15

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

问题：如何知道一个字符串是否可以分割成两个字符串 - 比如 breadbanana 可以分割成面包和香蕉，而 breadbanan 不能。您将获得一本包含所有有效单词的字典。

4

6 回答 6

13

构建字典中的单词，这将使搜索更快。根据输入字符串的以下字母搜索树。当您在树中找到一个单词时，递归地从输入字符串中该单词之后的位置开始。如果您到达输入字符串的末尾，您会发现一种可能的碎片。如果你被卡住了，回来递归地尝试另一个单词。

编辑：对不起，错过了一个事实，必须只有两个词。在这种情况下，将递归深度限制为 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 in 中的一个子节点O(1)（子节点的 ascii 索引），你可以在 中找到输入字符串的所有前缀O(n+p)，其中p是前缀的个数，以及n输入的长度。上限是O(n+m)，其中m是字典中的单词数。检查包含将采用O(w)wherew是单词的长度，其上限是m，因此算法的时间复杂度是O(nm)，因为O(n)它分布在所有找到的单词之间的第一阶段。

但是因为我们在第一阶段找不到更多的n词，所以复杂度也仅限于O(n^2). 所以搜索复杂度将是O(n*min(n, m)) 在此之前，您需要构建将采用的特里树O(s)，其中s是字典中单词长度的总和。上限是O(n*m)，因为每个单词的最大长度是n。

于 2013-03-06T07:28:13.690 回答
4

您浏览您的字典并将每个术语作为子字符串与原始术语（例如“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);
        }
    }
于 2013-03-06T07:39:39.800 回答
1

最简单的解决方案：

在每对连续字符之间拆分字符串，并查看两个子字符串（拆分点左侧和右侧）是否都在字典中。

于 2013-03-06T07:24:47.490 回答
0

一种方法可能是：

Put all elements of dictionary in some set or list 现在您可以使用contains&substring函数删除匹配字典的单词。如果最后字符串为空 -> 字符串可以被分段，否则不能。你也可以照顾计数。

于 2013-03-06T07:27:42.297 回答
0 
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。

于 2013-03-06T07:29:25.967 回答
0

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

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);
            }
        }

    }

}
于 2013-03-06T08:36:37.713 回答