首页 > 代码库 > Word Break

Word Break

这个题目思路:在一个bool型数组中,像接力一样传递匹配成功,传递到最后一个字符,说明匹配成功。说的明白点就是从第i(0~n)个字符开始向后与子串进行匹配,匹配的数组中标记为true,循环比较。

需要注意的是:unordered_set的count(T s)查看是否包含该元素。string类的substr(pos,n)函数返回从pos位置开始的n个字符。

 1 class Solution { 2 public: 3     bool wordBreak(string s, unordered_set<string> &dict) { 4         int MainLen = s.size(); 5         vector<bool> dp(MainLen,false); 6         dp[0] = true; 7         for(int i=0;i<MainLen;i++) 8         { 9             if(dp[i])10             {11                 for(int j = i;j<MainLen;j++)12                 {13                     if(dict.count(s.substr(i,j-i+1)))14                     {15                         dp[j+1] = true;16                     }17                 }18             }19         }20         return dp[MainLen];21     }22 };

 

Word Break