VIRTUALS

the virtual labs for the virtuals

0%

HJ27. 查找兄弟单词

Posted on Edited on In , , ,

摘要：
字符串TopK问题。

题目

描述
定义一个单词的“兄弟单词”为：交换该单词字母顺序（注：可以交换任意次），而不添加、删除、修改原有的字母就能生成的单词。
兄弟单词要求和原来的单词不同。例如：$ab$ 和 $ba$ 是兄弟单词。$ab$ 和 $ab$ 则不是兄弟单词。
现在给定你 $n$ 个单词，另外再给你一个单词 $str$，让你寻找 $str$ 的兄弟单词里，按字典序排列后的第 $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

字符串TopK

需要先将所有兄弟字符串筛选出来，再根据字典序拿到第 $K$ 大的那个。
首先判断兄弟字符串，复杂度最好可以达到 $O(N)$，可以维护计数数组实现。
$TopK$ 问题可以使用堆，或者排序。推荐堆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/**
 * author: etoa
 * code at: 2021-08-22 10:25:49
**/
#include <bits/stdc++.h>

using namespace std;

constexpr int N = 32;
int cnt1[N], cnt2[N];
int len;

struct cmp {
    bool operator()(string a, string b) {
        for (int i = 0, n = a.size(); i < n; i++) {
            if (a[i] != b[i]) return a[i] < b[i];
        }
        return true;
    }
};

inline bool isBrother(string a) {
    int n = a.size();
    if (n != len) return false;
    memset(cnt2, 0, sizeof cnt2);
    for (int i = 0; i < n; i++) cnt2[a[i] - 97]++;
    for (int i = 0; i < 32; i++) 
        if (cnt1[i] && cnt1[i] != cnt2[i]) return false;
    return true;
}

int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    vector<string> v;
    string s;
    int k;
    for (; cin >> n;) {
        string t;
        for (int i = 0; i < n; i++) {
            cin >> t;
            v.push_back(t);
        }
        cin >> s;
        cin >> k;
    }
    
    len = s.size();
    for (int i = 0; i < len; i++) cnt1[s[i] - 97]++;
    vector<string> bro;
    for (auto &each : v) {
        if (each.size() != len || each == s) continue;
        if (isBrother(each)) 
            bro.push_back(each);
    }
    priority_queue<string, vector<string>, cmp> max_heap;
    for (auto &each : bro) {
        max_heap.push(each);
        for (; max_heap.size() > k; max_heap.pop());
    }
    //for (; !max_heap.empty(); max_heap.pop()) cout << max_heap.top() << endl;
    cout << bro.size() << endl;
    cout << (max_heap.size() >= k ? max_heap.top() : "") << endl; 
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
 * author: etoa
 * code at: 2021-08-22 10:54:35
**/
import java.util.*;

public class Main {
    static final int N = 32;
    static int[] cnt1 = new int[N];
    private static void solve(Scanner in) {
        int n = in.nextInt();
        String[] ss = new String[n];
        for (int i = 0; i < n; i++) {
            ss[i] = in.next();
        }
        String s = in.next();
        int k = in.nextInt();
        int len = s.length();
        for (int i = 0; i < len; i++) {
            cnt1[s.charAt(i) - 97]++;
        }
        Queue<String> maxHeap = new PriorityQueue<>(new Comparator<String>() {
            @Override
            public int compare(String a, String b) {
                for (int i = 0, n = a.length(); i < n; i++) {
                    char ca = a.charAt(i);
                    char cb = b.charAt(i);
                    if (ca != cb) return cb - ca;
                }
                return 0;
            }
        });
        int broCnt = 0;
        for (String each : ss) {
            if (each.length() != len || each.equals(s)) continue;
            if (isBrother(each)) {
                broCnt++;
                maxHeap.add(each);
                for (; maxHeap.size() > k; maxHeap.poll());
            }
        }
        System.out.println(broCnt);
        if (maxHeap.size() >= k) System.out.println(maxHeap.peek());
    }
    
    private static boolean isBrother(String s) {
        int[] cnt2 = new int[N];
        for (int i = 0, n = s.length(); i < n; i++) {
            cnt2[s.charAt(i) - 97]++;
        }
        for (int i = 0; i < N; i++) {
            if (cnt1[i] != 0 && cnt1[i] != cnt2[i]) return false;
        }
        return true;
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        for (; in.hasNext();) {
            solve(in);
        }
    }
}

原题链接： HJ27. 查找兄弟单词