如何知道一个字符串是否可以分割成两个字符串

string algorithm java

2022-09-03 14:18:27

我在面试中被问到以下问题。我不知道该如何解决这个问题。请指导我。

问题：如何知道一根绳子是否可以分成两根弦 - 就像面包香蕉可以分割成面包和香蕉，而面包香蕉则不能。您将获得一个包含所有有效单词的字典。

答案 1

构建您在字典中的单词的三重奏，这将使搜索速度更快。根据输入字符串的以下字母搜索树。当您在树中找到一个单词时，请从输入字符串中该单词之后的位置递归开始。如果到达输入字符串的末尾，则发现一个可能的碎片。如果您遇到困难，请回来并递归尝试其他单词。

编辑：对不起，错过了事实，一定只有两个字。在这种情况下，请将递归深度限制为 2。

2 个单词的伪代码为：

T = trie of words in the dictionary
for every word in T, which can be found going down the tree by choosing the next letter of the input string each time we move to the child:
    p <- length(word)
    if T contains input_string[p:length(intput_string)]:
        return true
return false

假设您可以向下转到 trie 中的子节点（子项的 ascii 索引），则可以在中找到输入字符串的所有前缀，其中前缀数和输入的长度。其上限为，其中是字典中的单词数。检查包含将取单词的长度，其上限将是，因此算法的时间复杂度是，因为在第一阶段分布在所有找到的单词之间。O(1)O(n+p)pnO(n+m)mO(w)wmO(nm)O(n)

但是由于我们在第一阶段找不到的单词之外，因此复杂性也仅限于。因此，搜索复杂性将是在此之前，您需要构建将采取的trie，其中是字典中单词长度的总和。这个上限是，因为每个单词的最大长度是。nO(n^2)O(n*min(n, m))O(s)sO(n*m)n

答案 2

您浏览字典，并将每个术语作为子字符串与原始术语进行比较，例如“面包香蕉”。如果第一个词与第一个子字符串匹配，请从原始搜索词中删除第一个词条，并将下一个字典条目与原始词条的其余部分进行比较...

让我试着用java来解释一下：例如

    String dictTerm = "bread";
    String original = "breadbanana";

    // first part matches
    if (dictTerm.equals(original.substring(0, dictTerm.length()))) {
        // first part matches, get the rest
        String lastPart = original.substring(dictTerm.length());

        String nextDictTerm = "banana";

        if (nextDictTerm.equals(lastPart)) {
            System.out.println("String " + original +
                " contains the dictionary terms " +
                dictTerm + " and " + lastPart);
        }
    }