【算法四十五】139. 单词拆分

139. 单词拆分

动态规划：

class Solution { public boolean wordBreak(String s, List<String> wordDict) { //子问题:字符串的前 i 个字符能否用字典里的单词拼接 //状态转移方程:dp[i] = true if ∃ j ∈ [0, i) , dp[j] == true && s[j..i-1] ∈ wordDict //dp[i] = false //方向:从前到后 int n = s.length(); int maxLen = 0; for(String word:wordDict){ maxLen = Math.max(maxLen,word.length()); } //转化为Set是因为set的contains方法时间复杂度是O(1),List是O(n) Set<String> wordDicts = new HashSet<>(wordDict); boolean[] dp = new boolean[n+1]; dp[0] = true; //枚举前i个字符 for(int i = 1;i<=n;i++){ //枚举可划分的下标 for(int j = Math.max(0,i-maxLen);j<i;j++){ if(dp[j] && wordDicts.contains(s.substring(j,i))){ dp[i] = true; break; } } } return dp[n]; } }

时间复杂度：O(N*M)，N是字符串长度，S是最长单词长度

空间复杂度：O(N)