139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

思路：

简单的DP。看数据比较小，两重循环。

dp[i]表示前i个字符是否能够由单词表的中的单词组成。

代码：

  1. class Solution {
  2. public:
  3.     bool wordBreak(string s, vector<string>& wordDict) {
  4.         set<string> st;
  5.         for(string x:wordDict){
  6.             st.insert(x);
  7.         }
  8.         int n=s.size();
  9.         vector<int> dp(n+1,0);
  10.         string tm=s.substr(0,1);
  11.         dp[0]=1;
  12.         for(int i=1;i<=n;i++){
  13.             int ok=0;
  14.             for(int j=0;j<i;j++){
  15.                 if(dp[j]&&st.count(s.substr(j,i-j))) {
  16.                     ok=1;
  17.                     break;
  18.                 }
  19.             }
  20.             dp[i]=ok;
  21.         }
  22.         return dp[n];
  23.     }
  24. };