java - 如何从给定的字母中找到最长的单词。

Question

假设我有

String letters="CATOPHAPY";

我有字典以数组的形式检查。

String[] dict=new String[996];

我如何从字母中构造最长的单词并用我以前拥有的 dict 中的 vocab 检查它

谢谢

Answer 1

1. 准备一个字典单词数组，但要对每个条目的字母进行排序；
2. 按单词大小对字典本身进行降序排序；
3. 按照与字典中相同的顺序对输入字符串中的字母进行排序；
4. 从上到下遍历字典并找到所有字母都出现在输入中的第一个条目。由于排序，这可以实现为 O(n)。

广告 1、3。

char[] toSort = original.toCharArray();
Arrays.sort(toSort);
String sorted = new String(toSort);

广告 2。

Arrays.sort(dict, (String a, String b) -> b.length() - a.length());

广告 4。

boolean isMatch(String dictWord, String inputWord) {
  for (int i = 0, j = 0; i < dictWord.length();) {
    if (j >= inputWord.length()) return false;
    char d = dictWord.charAt(i), n = inputWord.charAt(j);
    if (d < n) return false;
    if (d >= n) j++;
    if (d == n) i++;
  }
  return true;
}