题解 | #查找兄弟单词#

查找兄弟单词

https://www.nowcoder.com/practice/03ba8aeeef73400ca7a37a5f3370fe68

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String[] dict = new String[n];
        for (int i = 0; i < n; i++) {
            dict[i] = in.next();
        }
        String keyWord = in.next();

        List<SuperString> matchList = new ArrayList<>();
        int k = in.nextInt();
        SuperString superKeyWord = new SuperString(keyWord);
        for (String s : dict) {
            SuperString superString = new SuperString(s);
            if (superKeyWord.match(superString)) {
                matchList.add(superString);
            }
        }
        matchList.sort((a, b) -> a.raw.compareTo(b.raw));
        System.out.println(matchList.size());
        if (matchList.size() >= k) {
            System.out.println(matchList.get(k - 1).raw);
        }
        

    }

    static class SuperString {
        String raw;
        String featureStr;
        SuperString(String raw) {
            this.raw = raw;
            char[] chars = raw.toCharArray();
            Arrays.sort(chars);
            StringBuilder builder = new StringBuilder();
            builder.append(chars[0]);
            int count = 1;
            for (int i = 1; i < chars.length; i++) {
                if (chars[i] == chars[i - 1]) {
                    count ++;
                } else {
                    builder.append(count);
                    count = 1;
                    builder.append(chars[i]);
                }
            }
            builder.append(count);
            this.featureStr = builder.toString();
        }

        boolean match(SuperString string) {
            if (this.featureStr.equals(string.featureStr) && ! this.raw.equals(string.raw)) {
                return true;
            }
            return false;
        }
    }
}

全部评论
字符串匹配,一个字符串的兄弟子串穷举的话是 n!。最开始的想法就是hash 和 字符表record。但是26个字母比较 record 比较麻烦,所以直接使用 featureStr 代替,因为顺序无关,所以字符数组可以先排序。因为字符串长度 < =10 常数, 所以排序也是常数时间。匹配时间复杂度O(n)。 寻找第 k 大的值,我是直接排序了,O(nlgn),总体 O(nlgn)
点赞 回复 分享
发布于 2023-02-28 21:47 北京

相关推荐

嵌入式求职之路:可以看我经验😂,https://www.nowcoder.com/share/jump/73221730841876945
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
05-01 13:13
ecece:这么明目张胆虚报就业率啊
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务