단어 분할 golang 실현

묘사 하 다.
          s                wordDict,  s                         。

  :

               。
               。
   1:

  : s = "leetcode", wordDict = ["leet", "code"]
  : true
  :    true    "leetcode"        "leet code"。
   2:

  : s = "applepenapple", wordDict = ["apple", "pen"]
  : true
  :    true    "applepenapple"        "apple pen apple"。
                   。
   3:

  : s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
  : false

사고의 방향
    
1.    
dp[i]      i         
        dp[i] = true           s[0:j] s[j:i] 
   s[0:j]            dp[j] = true
s[j:i]         

    
dp[i] = dp[j] && s[j:i] in wordDict

이루어지다
func wordBreak(s string, wordDict []string) bool {
    l := len(s)
    dict := make(map[string]bool)
    dp := make([]bool, l+1)
    dp[0] = true

    for _, word := range wordDict{
        dict[word] = true
    }

    dict[""] = true

    for i := 0; i <= l; i++{
        for j :=0; j <= i; j++{
            if  _, ok := dict[s[j:i]];ok && dp[j] {
                dp[i] = true
            }
        }
    }

    return dp[l]
}

좋은 웹페이지 즐겨찾기