[leetcode]139. Word Break单词能否拆分

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.You may assume the dictionary does not contain duplicate words.

Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code".

 

题意：

给定字符串S和字典wordDict, 判断字符串S是否能由字典中的单词组合而成

 

思路：

用一维boolean数组记录是否能字符串S是否能被分隔

           l       e      e      t       c      o      d     e 

TFFFFFFFF012345678

  dp[0]初始化为true, 其他为default的false

  dp[s.length() + 1]

 

i = 1         j = 1,  dp[1] 为default F, 没必要再去验证wordDict.contains(s.substring(j,i))

               j = 0,  dp[0] 为 T ， 验证wordDict.contains(s.substring(0,1)) 为F

i = 2        j = 2,  dp[2] 为default F

              j = 1,  dp[1] 为default F

　　　　  j = 0,  dp[0] 为 T ， 验证wordDict.contains(s.substring(0,2)) 为F

i = 3        j = 3,  dp[3] 为default F

              j = 2,  dp[2] 为default F

              j = 1,  dp[1] 为default F

　　　　  j = 0,  dp[0] 为 T ， 验证wordDict.contains(s.substring(0,3)) 为F

i = 4       j = 4, dp[4]为default F

　　　　 j = 3,  dp[3] 为default F

              j = 2,  dp[2] 为default F

              j = 1,  dp[1] 为default F

　　　　  j = 0,  dp[0] 为 T ， 验证wordDict.contains(s.substring(0,4)) 为T  ----> 更新dp[4] = true

TFFFTFFFF012345678

 

 

              

 

 

代码：

1 class Solution { 2 public boolean wordBreak(String s, List<String> wordDict) { 3 // corner case 4 if (s == null || s.length() < 1 || wordDict == null || wordDict.size() < 1) { 5 return false; 6 } 7 boolean[] dp = new boolean[s.length() + 1]; 8 dp[0] = true; 9 //外层循环scan字符串S 10 for(int i = 1; i <= s.length(); i++ ){ 11 //内层循环找分割点 12 for(int j = i; j >= 0; j--){ 13 if(dp[j] && wordDict.contains(s.substring(j,i))){ 14 dp[i] = true; 15 } 16 } 17 } 18 return dp[s.length()]; 19 } 20 }

 

转载于:https://www.cnblogs.com/liuliu5151/p/9075032.html