3

查找字符串的最长子序列 s，例如 "abccdde" 并给定字典 {"ab","add","aced"} 。上面示例的结果是“添加”

我在一次采访中被问到，我使用特里树给出了答案，最坏的情况是 O(n*m) ，n 是 s 的长度，m 是字典的长度。但我的平均成本应该很低。我没有通过面试，因为面试官认为我的解决方案不是最好的。有没有人有更好的主意？

4

5 回答 5

1

您可以创建一个图形，然后顶点就是您的字母表。对于字典中的每个单词，您将在图表中添加第一个字符，例如：

G[word[0]].add({word, 0})

然后，当您访问每个字母的文本时，您会访问该字母的 adyacency 列表。对于列表中的每个项目，您应该为该单词添加下一个字符。

用你的例子：

S = "abccdde", D = {"ab","add","aced"}

第一步：

G = {{'a', [{"ab", 0}, {"add", 0}, {"aced", 0}]}}

对于 S 中的每个字符

  • 字符 = 'a' -> S[0]

您访问该角色的列表

[{"ab", 0}, {"add", 0}, {"aced", 0}]

并更新您的图表

G = {{'b', [{"ab", 1}]}, {'d', ["add", 1]}, {'c', [{"aced", 1}]}}
  • 字符 'b' -> S[1]

您访问该角色的列表

[{"ab", 1}]

并更新您的图表

G = {{'d', ["add", 1]}, {'c', [{"aced", 1}]}}

当你完成“ab”时，你可以尝试改进你的答案。

  • 字符 'c' -> S[2]

您访问该角色的列表

[{"aced", 1}]

并更新您的图表

G = {{'d', ["add", 1]}, {'e', [{"aced", 2}]}}
  • 字符 'c' -> S[3]

该字符没有列表，然后您继续下一个字符

  • 字符 'd' -> S[4]

您访问该角色的列表

["add", 1]

并更新您的图表

G = {{'d', ["add", 2]}, {'e', [{"aced", 2}]}}

...

于 2016-12-17T17:33:55.517 回答
0

你可以使用这个方法

public static Boolean IsSubsequence(string ch, string item)
{
    if (ch.Length < item.Length)
    {
        return false;
    }
    int indexItem = 0;
    int indexCh = 0;
    while (indexCh < ch.Length && indexItem< item.Length)
    {
        if (ch[indexCh] == item[indexItem])
        {
            indexItem++;
        }
        indexCh++;
    }
    return indexItem == item.Length;
}

它是 o(n) 方法您也可以从按单词长度对字典项目进行排序开始，所以第一个返回 true 的将是结果

于 2016-10-21T09:13:13.630 回答
0

我认为不可能只使用一个循环来减少算法所花费的时间，至少它需要两个循环我猜，这是我的方法：

public String lookFor(String inputWord, String[] dictionary) {

  Arrays.sort(dictionary);

  for (int index = dictionary.length - 1; index > 0; index--) {
    if (isTheWordASubsequence(inputWord, dictionary[index]))
      return dictionary[index];
  }

  return null;
}

private boolean isTheWordASubsequence(String inputWord,
    String dictionaryWord) {

  int spot = 0;
  int offset = 0;

  for (char item : dictionaryWord.toCharArray()) {
    spot = (offset = inputWord.indexOf(item, spot)) >= spot ? offset : -1;
    if (spot < 0)
      return false;
  }

  return true;
}
于 2018-05-25T19:02:30.490 回答
0

安排您的字典数据结构，以便对于每个有效字母，您可以更深入地进入树（查看长一个字母的单词），并添加一个默认大小写（没有与此前缀匹配的字母）指向比当前深度（还有一个标志，表明您已经有一个词，以防万一结果是您的最佳选择）。

当您错过“asparag”后跟“r”时，如果有任何此类单词，您的字典会将您定向到“sparag”树，如果没有，则将您定向到“parag”。

对于每次失败，如果仍然没有匹配，您重复测试并递归到更短的单词；所以这仍然比 O(n) 更糟糕......尽管片刻的随意思考表明最坏的情况可能是 O(2n)。

为了加快速度，默认值可以是一个默认值列表，您可以从中选择与当前字母匹配的条目。所有条目将至少匹配长度为 0（当前字母无词开头）或 1（仅当前字母）的条目。

于 2016-12-17T18:01:52.907 回答
0

这是我的 Python 代码，用于时间复杂度为 O(N + L) 的解决方案，其中 N 是字符串中的字符数（对于“abccdde”，N = 7），L 是字典中的字符总数（对于 {"ab","add","aced"})，L = 9。基本上，它是线性时间复杂度。

def find_longest_word_in_string(string, words):
    m = {}

    for word in words:
        m[word] = 0

    for c in string:
        for word in m.keys():
            if len(word) == m[word]:
                continue
            else:
                if word[m[word]] == c:
                    m[word] += 1

    length = 0
    for word in m.keys():
        if m[word] == len(word) and m[word] > length:
            res = word
            length = m[word]

    return res

if __name__ == '__main__':
   s = "abccdde"                 
   words = ["ab","add","aced"]    
   print find_longest_word_in_string(s, words)

运行它，返回“添加”

于 2017-10-18T17:35:33.913 回答