如何判断一个字符串是否可以分割成两个子串

Question

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

问题：如何判断一个字符串是否可以分割成两个字符串 - 比如breadbanana可以分割成bread和banana，而breadbanan则不能。你将获得包含所有有效单词的字典。

- Bhaskar

---

我认为他要求两者兼备。 - Blizzer

Answer 1

构建一个字典树trie，这将使搜索更快。根据输入字符串的以下字母搜索树。当您找到树中的单词时，请从输入字符串中该单词后面的位置递归地开始。如果您到达输入字符串的末尾，则找到了一种可能的分段。如果您卡住了，请回来并递归地尝试另一个单词。

编辑：抱歉，错过了只需要两个单词的事实。在这种情况下，将递归深度限制为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树中以O(1)(子节点的ASCII索引)的时间复杂度到达子节点，那么在O(n+p)的时间复杂度内，你可以找到输入字符串的所有前缀，其中p是前缀数，n是输入长度。这个上限是O(n+m)，其中m是字典中单词的数量。检查是否包含将花费O(w)，其中w是单词长度，其上限将是m，因此算法的时间复杂度是O(nm)，因为O(n)在第一阶段被分配给找到的所有单词。

但是由于我们不能在第一阶段找到超过n个单词，所以复杂度也受到限制，最高为O(n^2)。 因此搜索复杂度将是O(n*min(n,m))。 在此之前，您需要构建Trie树，这将花费O(s)的时间复杂度，其中s是字典中所有单词长度的总和。这个上限是O(n*m)，因为每个单词的最大长度是n。

- Michał Trybus

---

有趣。我的想法是使用 trie 来定位第一个单词，如果找到了，则在字典中进行快速、常数时间的搜索第二个单词。我认为这比大多数其他提出的解决方案都要好得多。无论如何，给你点赞。 - Perception

感知：这仍然是O(n)的搜索，不是吗？ - NPE

@MichałTrybus：如果你的答案中包含了所提出算法的时间复杂度，那将会非常有帮助。 - NPE

嗯，trie搜索的时间复杂度是O(m)，其中m是字符串的输入长度，而哈希查找当然是常数时间。 - Perception

@Perception：实际上哈希查找也是O(m)。对于字符串的合理哈希函数会扫描其中的字符。 - Eyal Schneider

Answer 2

您需要遍历您的词典，并将每个术语作为子字符串与原始术语进行比较，例如“breadbanana”。如果第一个术语与第一个子字符串匹配，则从原始搜索术语中切掉第一个术语，并将剩余的原始术语与下一个字典条目进行比较...

让我尝试用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);
        }
    }

- Blizzer

Answer 3

最简单的解决方案：

将字符串在每对相邻字符之间拆分，并查看左侧和右侧子字符串是否都在字典中。

- Alexey Frunze

---

给出负评的原因是什么？ - Alexey Frunze

Answer 4

一种方法可能是：

将字典的所有元素放入某个集合或列表中，现在您可以使用contains和substring函数来删除与字典匹配的单词。如果最终字符串为空 -> 字符串可以被分段，否则不能。您还可以注意计数。

- vikbehal

Answer 5

public boolean canBeSegmented(String s) {
    for (String word : dictionary.getWords()) {
        if (s.contains(word) {
            String sub = s.subString(0, s.indexOf(word)); 
            s = sub + s.subString(s.indexOf(word)+word.length(), s.length()-1);
        }

        return s.equals("");
    }
}

这段代码检查您提供的字符串是否可以被完全分段。它会检查字典中的单词是否在您的字符串中，然后进行减法操作。如果您想在此过程中进行分段，必须按照单词内部的顺序对减去的片段进行排序。

只需要两个单词就可以简化操作：

public boolean canBeSegmented(String s) {
    boolean wordDetected = false;

    for (String word : dictionary.getWords()) {
        if (s.contains(word) {
            String sub = s.subString(0, s.indexOf(word)); 
            s = sub + s.subString(s.indexOf(word)+word.length(), s.length()-1);

            if(!wordDetected) 
                wordDetected = true;
            else 
                return s.equals("");
        }

        return false;
     }
}

这段代码检查一个单词，如果字符串中还有另一个单词且仅有这两个单词，则返回 true，否则返回 false。

- Lukas Eichler

Answer 6

这只是一个简单的想法，如果你愿意，你可以更好地实现它。

package farzi;

import java.util.ArrayList;

public class StringPossibility {
    public static void main(String[] args) {
        String str = "breadbanana";
        ArrayList<String> dict = new ArrayList<String>();
        dict.add("bread");
        dict.add("banana");
        for(int i=0;i<str.length();i++)
        {
            String word1 = str.substring(0,i);
            String word2 = str.substring(i,str.length());
            System.out.println(word1+"===>>>"+word2);
            if(dict.contains(word1))
            {
                System.out.println("word 1 found : "+word1+" at index "+i);
            }
            if(dict.contains(word2))
            {
                System.out.println("word 2 found : "+ word2+" at index "+i);
            }
        }

    }

}

- Hussain Akhtar Wahid 'Ghouri'