将字符串拆分为单词

Question

我正在寻找一种最有效的算法，用于从字符串中生成所有可能的单词组合。例如：

Input String: forevercarrot

Output:

forever carrot
forever car rot
for ever carrot
for ever car rot

我能想到一种暴力的方法。（查找所有可能的子字符串并匹配）但是否有更好的方法呢？

- JP19

---

你的暴力算法方法是正确的。假设你收到的问题只是要求用外语单词来回答。 - Apalala

Answer 1

使用 前缀树 存储已知单词列表。可能像 myspell 这样的库已经这样做了。尝试使用现成的。

一旦找到匹配项（如“car”），就可以将计算分为两个分支：一个分支开始寻找新单词（如“rot”），另一个继续探索当前起始词的变体（如“carrot”）。

有效地，您需要维护一个队列，其中包含每次拆分计算时字符串中的偏移量对 (start_position, current_position)。多个线程可以同时从该队列中弹出并尝试继续以 start_position 开始，但在 current_position 之前已经已知的单词，但该单词还未结束。当找到单词时，它会被报告，并从队列中弹出另一对。当不可能时，不生成结果。当进行拆分时，新对将添加到队列的末尾。最初，队列包含一个 (0,0)。

- 9000

---

请确保不要重复计算“carrot”的拆分两次 - 一次是为了“forever”，一次是为了“for ever”。缓存部分结果：对于每个[i..n]，设置（可能的拆分）集合。 - Martin Konicek

Answer 2

请参考这个问题，它有更好的答案。这是一个标准的动态规划问题：

如何将字符串拆分为单词。例如："stringintowords" -> "String Into Words"?

- Martin Konicek

Answer 3

通过伪代码实现，利用字符串的每个部分都必须是一个单词的事实，我们不能跳过任何内容。我们从字符串的开头向前工作，直到第一位是一个单词，然后生成其余字符串的所有可能组合。一旦完成这个步骤，我们继续前进，直到找到第一个单词的其他可能性，以此类推。

allPossibleWords(string s, int startPosition) {
    list ret
    for i in startPosition..s'length
        if isWord(s[startPosition, i])
            ret += s[startPostion, i] * allPossibleWords(s, i)
    return ret    
}

这段代码中的问题在于你最终会重复计算 - 在你的例子中，你将不得不两次计算allPossibleWords("carrot") - 一次在["forever", allPossibleWords["carrot"]]中，另一次在["for", "ever", allPossibleWords["carrot"]]中。因此，备忘录化是需要考虑的。

- Anon.

Answer 4

输入字符串：forevercarrot

输出：

forever carrot forever car rot for ever carrot for ever car rot

程序：

#include<iostream>
#include<string>
#include<vector>
#include<string.h>
void strsplit(std::string str)
{
   int len=0,i,x,y,j,k;
   len = str.size();
   std::string s1,s2,s3,s4,s5,s6,s7;
   char *c = new char[len+1]();
   char *b = new char[len+1]();
   char *d = new char[len+1]();
   for(i =0 ;i< len-1;i++)
   {
       std::cout<<"\n";
       for(j=0;j<=i;j++)
       {
          c[j] = str[j];
          b[j] = str[j];
          s3 += c[j];
          y = j+1;
       }
       for( int h=i+1;h<len;h++){
          s5 += str[h];
       }
       s6 = s3+" "+s5;
       std::cout<<" "<<s6<<"\n";
       s5 = "";
       for(k = y;k<len-1;k++)
       {
          d[k] = str[k];
          s1 += d[k];
          s1 +=  " ";
          for(int l = k+1;l<len;l++){
           b[l] = str[l];
           s2 += b[l];
         }
       s4 = s3+" "+s1+s2;
       s7 = s4;
       std::cout<<" "<<s4<<"\n";
       s3 = "";s4 = "";
       }
       s1 = "";s3 = "";
    }
}

int main(int argc, char* argv[])
{
    std::string str;
    if(argc < 2)
                std::cout<<"Usage: "<<argv[0]<<" <InputString> "<<"\n";
    else{
                str = argv[1];
                strsplit(str);
    }

return 0;
}

- sssss