java - 如何使用 Java 在复合词/简单词中定位简单词？

Question

我有一个包含“简单”和“复合”词的单词列表，我想实现一个算法来打印出一个没有由简单词组成的复合词的单词列表。

示例输入:

chat, ever, snapchat, snap, salesperson, per, person, sales, son, whatsoever, what, so

期望的输出:

chat, ever, snap, per, sales, son, what, so

我写了以下内容，但不知道如何从这里开始:

private static String[] find(String[] words) {

    ArrayList<String> alist = new ArrayList<String>();
    Set<String> r1 = new HashSet<String>();
    for(String s: words){
        alist.add(s);
    }
    Collections.sort(alist,new Comparator<String>() {

        public int compare(String o1, String o2) {

            return o1.length()-o2.length();
        }
    });

    int count= 0;
    for(int i=0;i<alist.size();i++){
        String check = alist.get(i);
        r1.add(check);
        for(int j=i+1;j<alist.size();j++){

            String temp = alist.get(j);
            //System.out.println(check+" "+temp);
            if(temp.contains(check) ){

                alist.remove(temp);

            }
        }
    }
    System.out.println(r1.toString());
    String res[] = new String[r1.size()];
    for(String i:words){
        if(r1.contains(i)){
            res[count++] = i;
        }
    }

    return res;
}

任何关于更好方法的指导/见解或建议都将不胜感激。

Answer 1

我试图检查您的代码，看起来“儿子”不在您的输出中。我相信它失败是因为这一行:

if(temp.contains(check)) { <-- wrong check.
    alist.remove(temp); 
}

因此，不是简单地检查 temp.contains(check) 是否存在，您应该有一个执行以下操作的小循环:

1. temp 是否以 check 开头？
2. 如果1)通过，则让temp = temp.substring(check.length)，然后再回到1)，直到temp == "";

另一种实现方式是设置一个 trie ( https://en.wikipedia.org/wiki/Trie) 并使用它进行检查？

1. 根据单词长度对单词列表进行排序
2. foreach这个词，如果这个词不在trie中，就把它加入到trie中。否则，这是一个重复词或复合词
3. 使用 DFS 将 trie 树输出到单词列表中。

第 1 步确保当您检查复合词时，它的简单词已经在 trie 中。