首页 > 试题广场 >

查找兄弟单词

[编程题]查找兄弟单词
  • 热度指数:375023 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
定义一个单词的“兄弟单词”为:交换该单词字母顺序(注:可以交换任意次),而不添加、删除、修改原有的字母就能生成的单词。
兄弟单词要求和原来的单词不同。例如: ab 和 ba 是兄弟单词。 ab 和 ab 则不是兄弟单词。
现在给定你 n 个单词,另外再给你一个单词 x ,让你寻找 x 的兄弟单词里,按字典序排列后的第 k 个单词是什么?
注意:字典中可能有重复单词。

数据范围:,输入的字符串长度满足

输入描述:
输入只有一行。
先输入字典中单词的个数n,再输入n个单词作为字典单词。
然后输入一个单词x
最后后输入一个整数k


输出描述:
第一行输出查找到x的兄弟单词的个数m
第二行输出查找到的按照字典顺序排序后的第k个兄弟单词,没有符合第k个的话则不用输出。
示例1

输入

3 abc bca cab abc 1

输出

2
bca
示例2

输入

6 cab ad abcd cba abc bca abc 1

输出

3
bca

说明

abc的兄弟单词有cab cba bca,所以输出3
经字典序排列后,变为bca cab cba,所以第1个字典序兄弟单词为bca         
while True:
    try:
        ls = list(input().split()) # 将所有输入存储在列表ls中
        n = int(ls[0]) # 获取输入单词的个数n
        ls.pop(0)    # 从原列表中删除n
        k = int(ls.pop()) # 获取列表ls最后的值,即待查找的位置k(即删除最后的元素,存入k)
        # !!!这里注意k需要转换为整数类型!!!
        
        # 上面两步经过pop()方法的操作,得到更新后的列表ls。
#         print(ls)
        x = ls[-1] # 获取更新后的列表ls中的最后一个值x
#         print(x)
        
        # 判断输入的n个单词是否是x的兄弟单词并存入列表lsn中
        lsn = []
        for i in range(n):
            if ls[i] != x and sorted(ls[i]) == sorted(x):
                lsn.append(ls[i])
        # 接下来对lsn按字典顺序进行排序
        lsn.sort()
#         print(lsn)
        
        # 最后输出结果
        length = len(lsn)
        print(length)
        if k <= length:
            print(lsn[k-1])
    except:break
虽然分类的困难,但其实题目读懂,真的写起来并不难,就是一个一个判断,就是代码有点多。
发表于 2021-08-09 10:24:12 回复(6)
#这题够坑,后面输出判定,调试了很久。。。。
while True:
    try:
        ls=list(raw_input().split())
        s=ls[-2]
        lm=ls[1:-2]
        ll=[]
        count=0
        for i in lm:
            if s!=i:
                m=list(s)
                m.sort()
                n=list(i)
                n.sort()
                if "".join(m)=="".join(n):
                    count+=1
                    ll.append(i)
        ll.sort()
        if count!=0 and int(ls[-1])<=len(ll) and ll:
            print(count)
            print(ll[int(ls[-1])-1])
        elif count!=0 and int(ls[-1])>len(ll):
            print(count)
        elif count==0:
            print(count)
    except:
        break

发表于 2019-07-09 21:38:22 回复(1)
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] array = in.nextLine().split(" ");
        List<String> bro = new ArrayList<>();
        String pattern = array[array.length - 2];
        char[] temp = pattern.toCharArray();
        int count = 0;
        Arrays.sort(temp);
        String sortedPattern = String.valueOf(temp);
        for(int i = 1; i < array.length - 2; i++){
            //相同的单词
            if(array[i].equals(pattern)) continue;
            //不同的单词
            //先排序,再比对
            char[] cur = array[i].toCharArray();
            Arrays.sort(cur);
            String sortedCur = String.valueOf(cur);
            if(sortedCur.equals(sortedPattern)){
                bro.add(array[i]);
                count++;
            }
        }
        Collections.sort(bro);
        int index = Integer.valueOf(array[array.length - 1]);
        System.out.println(count);
        if( index <= count){
            System.out.println(bro.get(index - 1));
        }
    }
}
我笔试能遇到这么无聊的困难题,我就把牛客的题库打出来全吃了。
发表于 2021-01-02 22:07:50 回复(1)
//朋友们,这道题有2个坑,不怪大家不AC,就是出题人没说清楚(插会腰,可把自己牛逼坏了)
//1.输出分为2行,第一行为兄弟个数,第二行输出指定第几个兄弟,要是没有就不输出。
//2.找出的兄弟要以字典序排列
#include<iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int const maxNum = 1000 + 1;

bool equSring(string a,string b);  //b是不是就是a
bool isBrother(string a,string b); //b是不是a的兄弟
bool cmp(string a ,string b){      //字典序排列
	return a<b;  
}
int main(){
	int n;
	while(cin>>n){
		string inp1[maxNum];
		for(int i=0;i<n;i++) cin>>inp1[i];
		string lookAns;
		int posAns;
		cin>>lookAns>>posAns;
		vector<string> aa;
		for(int i=0;i<n;i++){
			if(isBrother(lookAns,inp1[i])){
				aa.push_back(inp1[i]);
			}
		}
		sort(aa.begin(),aa.end(),cmp);
		if(posAns<=aa.size()){
			cout<<aa.size()<<endl;
			cout<<aa[posAns-1]<<endl;
		}else
			cout<<aa.size()<<endl;
	}
	return 0;
}
bool equSring(string a,string b){
	return a.compare(b);
}
bool isBrother(string a,string b){ //b是不是a的兄弟

	if((a.length() ==b.length())&&(equSring(a,b))){
		int len = b.length();
		char* p = new char[len];
		for(int i=0;i<len;i++) p[i]=b[i];
		sort(p,p+len);
		char* pp = new char[len];
		for(int i=0;i<len;i++) pp[i]=a[i];
		sort(pp,pp+len);
		for(int i=0;i<len;i++){
			if(p[i]!=pp[i]){
				delete p;
				delete pp;
				return false;
			}   
		}
		delete p;
		delete pp;
		return true;

	}else
		return false;
}

发表于 2017-05-31 12:09:37 回复(2)
def is_brother(str1, str2):
    if str1 == str2:
        return False
    str1 = "".join(sorted(str1))
    str2 = "".join(sorted(str2))
    if str1 == str2:
        return True
    return False

while True:
    try:
        input_list = input().split()
        word_list, word, k = input_list[1:-2], input_list[-2], int(input_list[-1])
        brother_list = []
        for sub in word_list:
            if is_brother(word, sub):
                brother_list.append(sub)
        brother_list = sorted(brother_list)
        print(len(brother_list))
        print(brother_list[k-1])
    except:
        break

发表于 2022-07-18 00:26:32 回复(0)
const n = arr[0];
const x = arr[arr.length - 2];
const k = arr[arr.length - 1];
const newArr = [...arr]
const res = []
newArr.shift()
newArr.pop()
newArr.pop()
newArr.forEach(item=>{
    if(item.length === x.length && item.split('').sort().join('') === x.split('').sort().join('') && item !== x){
        res.push(item)
    }
})
console.log(res.length)
if(k-1<res.length){
    console.log(res.sort()[k-1])
}

发表于 2022-07-05 15:54:22 回复(0)
while True:
    try:
        data = input().split()
        bro_len = int(data[0])
        k = int(data[-1])
        temp = data[-2]
        words = data[1:-2]
        assert len(words) == bro_len, print('the length must be the same')
        bros = []
        for word in words:
            if sorted(word.lower()) == sorted(temp.lower()) and (not word==temp):
                bros.append(word)
                
        sorted_bros = sorted(bros, )
        
        print(len(bros))
        print(sorted_bros[k-1])        
    except:
        break

这个题比较简单,用暴力法即可解决。
先判断每个单词是否是模板单词的兄弟单词: if sorted(word.lower())==sorted(temp.lower()) and (not word==tempt)
然后将兄弟单词存储起来
最后将存储起来的兄弟单词按照字母顺序排列sorted(bors)

发表于 2022-06-25 16:09:06 回复(0)
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

class Solution
{
  public:
    void FindBrotherWord(const vector<string>& strs,const int& strs_size,const string& tar_str,const int& tar_index)
    {
        vector<string> brother_word;//存放所有兄弟单词的数组
        for(int i = 0; i < strs_size;i++)
        {
            //如果字符串个数相等,但是直接比较不等的情况
            if( (strs[i].size() == tar_str.size() ) && (strs[i] != tar_str))
            {
                string tar_tmp = tar_str;//暂时存放目标字符串
                string init_tmp = strs[i];//存放原字符串的字符
                sort(tar_tmp.begin(), tar_tmp.end());//两种分别排序后再判断是否相等
                sort(init_tmp.begin(), init_tmp.end());
                if(tar_tmp == init_tmp)//如果相等,保存到兄弟单词数组中
                {
                    brother_word.push_back(strs[i]);
                }
            }
        }
       sort(brother_word.begin(),brother_word.end());
        //查找索引
       if(tar_index > brother_word.size())//比兄弟个数要多
           cout << brother_word.size() << endl;
       else
       {
           cout << brother_word.size() << endl;
           cout << brother_word[tar_index-1] << endl;
       }
           
    }
};

int main()
{
    int i = 0;
    vector<string> strs;
    int strs_num = 0;//字典序中单词的个数
    string tar_str;//目标单词
    int tar_index; //要查找的兄弟单词在兄弟单词集的索引位置
    string str;
    while(cin >> str)
    {
        if(i == 0)
            strs_num = stoi(str);
        else if( i > 0 && i <= strs_num)
            strs.push_back(str);
        else if( i == (strs_num + 1))
            tar_str = str;
        else
            tar_index = stoi(str);
        i++;
    }
     Solution s;
     s.FindBrotherWord(strs,strs_num,tar_str, tar_index);
   
    //测试输入
    /*
    cout << strs_num << endl;
    for(auto p : strs)
    {
        cout << p << endl;
    }
    cout << tar_str << endl;
    cout << strs_index << endl;*/
    
   
    
    
    return 0;
}

发表于 2022-06-20 11:14:02 回复(0)
题目中的第一个  先输入字典中单词的个数n 有什么用?
def test(s: str):
    num, *lis, x, k = s.split(' ')
    k = int(k)
    result = sorted([i for i in lis if x != i and sorted(x) == sorted(i)])
    print(len(result))
    if len(result) >= k:
        print(result[k - 1])


if __name__ == '__main__':
    try:
        test(input())
    except EOFError:
        pass

发表于 2022-05-26 16:16:20 回复(0)
// 题目细节容易忽略,其他还好

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        List<String> list = new ArrayList<>();

        while (n > 0) {
            list.add(sc.next());
            n--;
        }

        String target = sc.next();
        int k = sc.nextInt();

        List<String> brother = new ArrayList<>();
        int count = 0;
        for (String s : list) {
            if (!s.equals(target) && isBrotherWord(s, target)) {
                brother.add(s);
            }
        }
        
        Collections.sort(brother);
        
        System.out.println(brother.size());
        if (brother.size() >= k) {
            System.out.println(brother.get(k - 1));
        }
        
    }

    public static boolean isBrotherWord(String s1, String s2) {

        char[] chs1 = s1.toCharArray();
        char[] chs2 = s2.toCharArray();

        Arrays.sort(chs1);
        Arrays.sort(chs2);

        return String.valueOf(chs1).equals(String.valueOf(chs2));
    }
}

发表于 2022-05-21 18:11:24 回复(0)
while True:
    try:
        n,*lst,x,k = list(input().split())
        new = [i for i in lst if sorted(i) == sorted(x) and i!= x]
        new = sorted(new)
        print(len(new))
        if len(new)>=int(k):
            print(new[int(k)-1])
    except:
        break
        
发表于 2022-05-15 01:08:35 回复(1)
这个题目也太坑了,按字典序,我以为是按这个说的单词字典的原始顺序,原来结果是按abcd的这种字典序
发表于 2022-05-03 22:14:03 回复(0)
while True:
    try:
        list_a = list(input().split(sep=' '))
        word = list_a[-2]
        num = int(list_a.pop())
        new_list = []
        for i in list_a:
            if sorted(i) == sorted(word) and i != word:
                    new_list.append(i)
        res = sorted(new_list)
        print(len(res))
        print(res[num-1])
    except:
        break

发表于 2022-04-23 17:26:04 回复(0)
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        String [] word = str.split(" ");
        int len = word.length;
        String xWord = word[len -2];
        int k = Integer.parseInt(word[len -1]) ;
        String xSort = sortStr(xWord);
        // list保留所有的兄弟节点
        List<String> list = new ArrayList();
        for(int i=0;i<=len-3;i++){
            if(!xWord.equals(word[i]) 
               && xWord.length() == word[i].length()
               && xSort.equals(sortStr(word[i]))){
                list.add(word[i]);
            }
        }
        System.out.println(list.size());
        Collections.sort(list);
        if(list.size() > k ){
            System.out.print(list.get(k - 1));
        }
    }
    
    static String sortStr(String str){
        char [] chars = str.toCharArray();
        Arrays.sort(chars);
        return String.valueOf(chars);
    } 
}
发表于 2022-03-12 08:05:42 回复(0)

判断是否是兄弟字符的两种方法:

  1. 对两个字符串都按照同样的字典序排序,排序完后相同,则为兄弟字符
  2. 先使用dfs暴搜生成所有的兄弟字符数组表,再到其中查表找;
    比较后,两个方法的时间复杂度差不多
发表于 2022-03-09 23:23:01 回复(1)

当务之急是对输入的各个字符串,分辨出其中哪些字符串是给定字符串的兄弟单词。由题意可知,当两个字符串长度不等时,或两个字符串内容一摸一样时,它俩必然不是兄弟关系;当两个字符串长度相等,同时各索引位置对应的字符不全相等,但是构成各字符串的字符种类及其频次相等时,这两个字符串互为兄弟。
先从原始输入顺序的字符串序列中筛选出兄弟单词,并存入数组或数组链表等容器中,对容器中的字符串进行排序。如果对于容器存储元素的个数length,目标次序k有效,即k<=length,即可找到目标元素。理论上该方法可行,但对于本题提供的测试用例以及时间要求,运行结果表明该方法超出时间限制。分析一下,不难得知,因为这个处理过程不仅需要重新存储兄弟单词,还要对其进行排序,这两个任务不能同时进行。当输入的字符串数量很大时,当然要花费较多的时间,消耗较大的内存空间。但是,题目要求寻找有序的兄弟单词序列中的第k个兄弟单词,所以对兄弟单词序列进行排序是必需的。如果从原本就有序的字符串序列中依次筛查当前字符串是否为给定单词的兄弟单词,且同时计数,就可以在一次遍历过程结束时获悉目标结果。当计数值与k相等时,当前的字符串就是有序的第k个兄弟单词;如果直到遍历结束,计数值还小于k值,那么说明k值无效,没有找到有序的第k个兄弟单词。代码如下所示。

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        while (in.hasNext()) {
            int length = in.nextInt();

            String[] strArr = new String[length];
            for (int i = 0; i < length; i++) {
                strArr[i] = in.next();
            }

            String pattern = in.next();
            int k = in.nextInt();
            in.nextLine();

            getKthBroStr(pattern, strArr, k);
        }

        in.close();
    }

    private static void getKthBroStr(String pattern, String[] strArr, int k) {
        //查找strArr中pattern的兄弟单词顺序序列中的第k个

        Arrays.sort(strArr);
        //记录兄弟单词的个数
        int broCount = 0;
        //存储第k个兄弟单词
        String candidate = null;

        for (int i = 0; i < strArr.length; i++) {
            if (isBroStr(pattern, strArr[i])) {
                //如果数组中当前单词为兄弟单词,则broCount加一
                broCount++;
                //如果broCount值与k相等,即为目标
                if (k == broCount) candidate = strArr[i];
            }
        }

        System.out.println(broCount);
        if (candidate != null) {
            //如果找到了第k个兄弟单词,打印其,否则不打印
            System.out.println(candidate);
        }
    }

    private static boolean isBroStr(String pattern, String str) {
        //判断str是否为pattern的兄弟单词
        //如果两个字符串的长度不等,则不是兄弟
        if (pattern.length() != str.length()) return false;
        //如果两个字符串内容一摸一样,则不是兄弟,而是影子
        if (pattern.equals(str)) return false;

        char[] patternChars = pattern.toCharArray();
        char[] strChars = str.toCharArray();

        //对两个字符串对应的字符串组进行自然排序
        //如果排序后的两个数组各索引位置上对应的值相等,那这两个字符串互为兄弟,否则不是
        Arrays.sort(patternChars);
        Arrays.sort(strChars);

        return Arrays.equals(patternChars, strChars);
    }
}
发表于 2022-01-28 13:08:43 回复(0)
#include<iostream>
#include<set>
#include<string>
#include<vector>
#include<unordered_map>
std::pair<int, std::string> findBrother(std::vector<std::string>& arr,const std::string& findStr, int &k)
{
    size_t len = findStr.size();
    std::multiset<std::string> m;
    std::unordered_map<char, int> hash;
    for(auto &ch : findStr)
    {
        hash
[ch]++;
    }
    std::unordered_map<char, int> temp;
    
    for(auto & s: arr)
    {
        for(auto &ch : s)
        {
            temp
[ch]++;
        }
        bool flag = (temp == hash) ? true : false; 
        
        if(s != findStr && flag)
        {
            m.insert(s);
        }
        temp.clear();
    }
    
    int pos = static_cast<int>(m.size());
    std::string str;
    for(auto &s : m)
    {
        if(--k ==  0)
        {
            str = s;
            break;
        }
    }
    return std::make_pair(pos, str);
}

int main()
{
    int n;
    std::cin >>n;
    std::string str;
    std::vector<std::string> array(n);
    for(auto &s : array)
    {
        std::cin >>s;
    }
    std::string findStr;
    std::cin >>findStr;
    int k =0;
    std::cin >> k;
    std::pair<int, std::string> ret = findBrother(array, findStr, k);
    std::cout << ret.first << std::endl;
    std::cout << ret.second << std::endl;
    return 0;
}

编辑于 2022-01-19 16:14:45 回复(1)
算不上困难的题目,重点在于用排序的方法判断是否为兄弟单词
while True:
    try:
        s=input().split()
        m=int(s[0])
        t=list(s[len(s)-2])
        k=int(s[len(s)-1])
        s.pop(0)
        s.pop(len(s)-1)
        s.pop(len(s)-1)

        bro=[]
        for x,i in enumerate(s):
            i=list(i)
            if i!=t:
                if sorted(i)==sorted(t):
                    bro.append(s[x])

        print(len(bro))
        bro.sort()
        if k<=len(bro):
            print(bro[k-1])
    except:
        break

发表于 2021-12-06 18:38:17 回复(0)
判断是否兄弟单词
1. 单词长度不一致, false
2. 单词相等, false
3. 因为可以任意次交换,并且同一个单词中有相同字母的可能性,不能通过判断单词contains来判断。这里再次使用了全排列的算法。将需要判断的单词toCharArray后进行全排列,全排列结果中有等于target单词的,则是兄弟单词。
import java.util.*;

public class HJ27 {
    private static  String target;
    private  static List<String> brothers = new ArrayList<>();
    private static boolean flag = false;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str = sc.nextLine();
            String[] strArr = str.split(" ");
            int n = Integer.valueOf(strArr[0]);

            int k = Integer.valueOf(strArr[strArr.length-1]);

            target = strArr[strArr.length -2];


            for (int i =1; i<= n; i++) {
                String item = strArr[i];
                if (item.length() != target.length() || item.equals(target)) {
                    continue;
                }
                isBrother(item, 0);
                if(flag) {
                    brothers.add(item);
                }
                flag = false;
            }
            System.out.println(brothers.size());
            if (brothers.size() >= k) {
                brothers.sort((s1,s2) -> {
                    return s1.compareTo(s2);
                });
                System.out.println(brothers.get(k-1));
            }

            brothers.clear();
        }
    }

    private static void isBrother(String item, int m) {
        if (m == item.length() - 1) {
            if (item.equals(target)) {
                flag = true;
            }
        }
        // 对target的字母进行全排列
        for (int i=m; i < item.length();i++) {
             item = swap(item.toCharArray(), i, m);
             isBrother(item, m + 1);
             item = swap(item.toCharArray(), i, m);
        }
    }

    private static String swap(char[] arr, int m , int n) {
        char temp = arr[m];
        arr[m] = arr[n];
        arr[n] = temp;
        return String.valueOf(arr);
    }
}


发表于 2021-08-18 22:31:52 回复(0)
def broword(myword):
    res=[]
    def backtrack(word,temp):
        if not word:
            res.append(temp)
            return
        for i in range(len(word)):
            temp+=word[i]
            backtrack(word[:i]+word[i+1:],temp)
            temp=temp[:-1]
    backtrack(myword,"")
    j = res.index(myword)
    return res[:j]+res[j+1:]
while True:
    try:
        get=list(input().split())
        n=int(get[0])
        k=int(get[-1])
        myword=get[-2]
        words=get[1:-2]
        dic=broword(myword)
        res=[]
        for i in words:
            if i in dic:
                res.append(i)
        rlen=len(res)
        print(rlen)
        res=sorted(res)
        if k <= rlen:
            print(res[k-1])
    except:
        break

帮看一下怎么 结果不对
发表于 2021-08-18 15:39:07 回复(0)