Word Break--LeetCode

港控/mmm° 2022-08-07 12:55 2阅读 0赞

# 题目： #

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given  
s = `"leetcode"`,  
dict = `["leet", "code"]`.

Return true because `"leetcode"` can be segmented as `"leet code"`.

思路：使用DP比较合适，看需要保存的遍历，我们使用一个数组，包含当前字符之前的子字符串能够被word break，到最后一个字符如果仍然可以的话，说明可以被word break。遍历到第I个字符，看包含当前字符的所有前缀子串能否被break，如果某一个可以被分割并且之前的,加入从j到i个子串可以被分割，并且如果j==0或者flag\[j-1\]表示也可以分割，表明flag\[i\]也是可以分割，初始化数组为-1，可以分割初始化为可分割的长度。

#include <iostream>
    #include <string>
    #include <set>
    #include <vector>
    using namespace std;
    
    bool WordBreak(string str,set<string>& dict)
    {
        vector<int> flag(str.length(),-1);
        set<string>::iterator itr;
        int i,j;
        for(i=0;i<str.length();i++)
        {
            for(j=0;j<=i;j++)
            {
               string temp(str,j,i-j+1);
               itr = dict.begin();  
               for(;itr != dict.end();itr++)
               {
                 if(*itr == temp)
                 {
                    if(j==0 || flag[j-1] != -1)
                       flag[i] = temp.length();
                 }                    
               }           
            }                                 
        }
        if(flag.back() != -1)
         return true;
        else
         return false;
    }
    
    int main()
    {
        set<string> dict;
        dict.insert("wang");
        dict.insert("leet");
    
        dict.insert("code");
        dict.insert("zhong");
        dict.insert("ren");
        string str("wangcoderen");
        set<string>::iterator itr = dict.begin();
        cout<<WordBreak(str,dict);
        system("pause");
        return 0;
        }

贴一下别人的一个思路：

这道题仍然是动态规划的题目，我们总结一下动态规划题目的基本思路。首先我们要决定要存储什么历史信息以及用什么数据结构来存储信息。然后是最重要的递推式，就是如从存储的历史信息中得到当前步的结果。最后我们需要考虑的就是起始条件的值。

接下来我们套用上面的思路来解这道题。首先我们要存储的历史信息res\[i\]是表示到字符串s的第i个元素为止能不能用字典中的词来表示，我们需要一个长度为n的布尔数组来存储信息。然后假设我们现在拥有res\[0,...,i-1\]的结果，我们来获得res\[i\]的表达式。思路是对于每个以i为结尾的子串，看看他是不是在字典里面以及他之前的元素对应的res\[j\]是不是true，如果都成立，那么res\[i\]为true，写成式子是

![SouthEast][]

假设总共有n个字符串，并且字典是用HashSet来维护，那么总共需要n次迭代，每次迭代需要一个取子串的O(i)操作，然后检测i个子串，而检测是constant操作。所以总的时间复杂度是O(n^2)（i的累加仍然是n^2量级），而空间复杂度则是字符串的数量，即O(n)。代码如下：

public boolean wordBreak(String s, Set<String> dict) {  
            if(s==null || s.length()==0)  
                return true;  
            boolean[] res = new boolean[s.length()+1];  
            res[0] = true;  
            for(int i=0;i<s.length();i++)  
            {  
                StringBuilder str = new StringBuilder(s.substring(0,i+1));  
                for(int j=0;j<=i;j++)  
                {  
                    if(res[j] && dict.contains(str.toString()))  
                    {  
                        res[i+1] = true;  
                        break;  
                    }  
                    str.deleteCharAt(0);  
                }  
            }  
            return res[s.length()];  
        }

ps:

其实这个题目不使用动态规划也是可以解决，第一个思路应该想到使用字典树，对字典使用字典树的方法进行初始化，然后对字符串组成的子串在字典树中查找，如果字典树不会初始化的话，可以使用STL中的set来初始化字段，hash\_set也是可以的，因为set的底层也是红黑树，所以在查找的时候时间复杂度为log级别的

[SouthEast]: /images/20220805/ffea3233b56b41b4b54ec95b3ec3a43d.png