1、题目描述
输入一个字符串s和一个字符串数组dict。判断s是否可以由dict的一些字符串组成。
2、思路
动态规划。
dp[i][j]表示s的前i位用dict的前j个字符串能不能表示。
dp[0][i] = true;
如果dp[i][j-1] is true, then dp[i][j] is true.
dp[i-k][j] is true and s.substr(i-k,k) = dict[j] ,then dp[i][j] = true.
3、代码
bool wordBreak(string s, vector<string>& wordDict) { int l = s.size(); int n = wordDict.size(); bool dp[l+1][n+1]; for(int i=0;i<=l;i++){ for(int j=0;j<=n;j++) dp[i][j]=false; } for(int i=0;i<=n;i++) dp[0][i]=true; for(int i=1;i<=l;i++){ for(int j=1;j<=n;j++){ dp[i][j]=dp[i][j-1]; if(dp[i][j]) continue; for(int a = 0;a<j;a++){ int k = wordDict[a].size(); if(i-k>=0 && s.substr(i-k,k)==wordDict[a] && dp[i-k][j]){ dp[i][j] = true; break; } } } } return dp[l][n]; }bool wordBreak(string s, vector<string>& wordDict) { int n = s.size(); int l = wordDict.size(); bool dp[n+1]={false}; dp[0]=true; for(int i=1;i<=n;i++){ for(int j=0;j<l;j++){ int a = wordDict[j].size(); if(i-a>=0 && s.substr(i-a,a)== wordDict[j] && dp[i-a]){ dp[i] = true; break; } } } return dp[n]; } 这个复杂度小。
