【每日一题】- leetcode- 139. 单词拆分

 判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
 
 输入: s = "applepenapple", wordDict = ["apple", "pen"]
 输出: true
 解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。

 1. 时间复杂度：O(n^n)
  考虑最坏情况 s = {aaaaaaa} 。每一个前缀都在字典中，此时回溯树的复杂度会达到 n^n
 
 2. 空间复杂度：O(n) 。回溯树的深度最深达到 n。

 n-1+n-2+n-3+ .....+ 3 +2 +1 =(1+n)*n/2
 =O(n^n)

 func wordBreak(s string, wordDict []string) bool {
     
     return helper(s,wordDict,0)
     
 }
 
 
 func helper(s string,wordDict []string,start int) bool {
     
     if start >=len(s) {
         return true
     }
     
     for i:=start;i < len(s);i++{
         
         if getWord(s[start:i+1],wordDict) ==true && helper(s,wordDict,i+1) ==true {
     
             return true
         }
     }
     
     return false
 }
 
 func getWord(word string,wordDict []string) bool {
     
     for i:=0; i < len(wordDict);i++ {
         if  word == wordDict[i] {
             return true
         }
         
     }
     
     return false
 }

 public class Solution {
     public boolean wordBreak(String s, List<String> wordDict) {
         return word_Break(s, new HashSet(wordDict), 0, new Boolean[s.length()]);
     }
     public boolean word_Break(String s, Set<String> wordDict, int start, Boolean[] memo) {
         if (start == s.length()) {
             return true;
         }
         if (memo[start] != null) {
             return memo[start];
         }
         for (int end = start + 1; end <= s.length(); end++) {
             if (wordDict.contains(s.substring(start, end)) && word_Break(s, wordDict, end, memo)) {
                 return memo[start] = true;
             }
         }
         return memo[start] = false;
     }
 }

 输入: s = "leetcode", wordDict = ["leet", "code"]
 输出: true
 解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

 func wordBreak(s string, wordDict []string) bool {
     
     //题目中说非空字符串，以下 assert 一定通过
     if len(s)  == 0 {
         return true 
     }
     
     // 状态定义：长度为 i 的子串可以被空格拆分为一个或多个在字典中出现的单词
     dp:=make([]bool,len(s)+1)
     // 这个状态的设置非常关键，说明前部分的字符串已经在 wordSet 中
     dp[0] =true // s 是空字符串
     
     // 判断逻辑
     //使用 r 表示右边界，可以取到
     //使用 l 表示左边界，也可以取到
     //[0 AA left BBB right]
     //拆分n个单词
     for right:=1;right<=len(s);right++ {
         
         for left:=0;left < right;left++ {
             //同时为上层下一次计算 提供方面
             // dp[left] 写在前面会更快一点，否则还要去切片，然后再放入 hash 表判重
             if dp[left] ==true && getWord(s[left:right],wordDict) ==true {
                 dp[right] =true //依赖下层：子串，判断子串只要一个存在在
                  // 这个 break 很重要，一旦得到 dp[r] = True ，循环不必再继续
                 break
             }
         }
     }
     
     return dp[len(s)]
 }
 
 
 
 
 func getWord(word string,wordDict []string) bool {
     
     for i:=0; i < len(wordDict);i++ {
         if  word == wordDict[i] {
             return true
         }
         
     }
     
     return false
 }