string - 给定没有空格的短语，添加空格以构成适当的句子

这就是我的想法，但它是O(n ^ 2):

例如:输入为“Thisisawesome”，我们需要检查是否添加了当前字符会使较早的发现集不再有意义。但是，为了查看直到需要备份的地方，我们必须从头到尾进行遍历。例如:“awe”和“some”构成适当的词，而“awesome”构成较大的词。请提出如何改善复杂性的建议。这是代码:

void update(string in)
{
   int len= in.length();
   int DS[len];
   string word;
   for(int i=0; i<len; i++) DS[i]=0;

   for(int i=0; i<len; i++)
        for(int j=i+1; j<=len; j++)
        {
            word = in.substr(i,j-i);
            if(dict.find(word)!=dict.end())
                   DS[j-1] = (DS[j-1] > word.length()) ? DS[j-1] : word.length();
         }
}

最佳答案

有一种动态编程解决方案，起初看起来像是O(n ^ 2)，但对于足够大的n和固定大小的字典，结果只有O(n)。

从左到右浏览字符串。在第i阶段，您需要确定前i个字符是否存在解决方案。要解决此问题，请考虑将这些i字符分成两个大块的所有可能方法。如果第二个块是一个单词，而第一个块可以分解成多个单词，那么有解决方案。您可以查询字典的第一个要求。您可以通过查看是否找到第一个j个字符的答案来检查第二个要求，其中j是第一个块的长度。

这将是O(n ^ 2)，因为对于1,2,3，... n个长度中的每一个，您都会考虑每个可能的分割。但是，如果您知道字典中最长的单词是什么，那么您就知道没有必要考虑使第二个块长于此的分割。因此，对于1,2,3 ... n个长度中的每个长度，您最多考虑w个可能的拆分，其中w是字典中最长的单词，代价为O(n)。