LeetCode: Word Break

Posted on February 26, 2018July 26, 2020 by braindenny

Word Break

Similar Problems:

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. You may assume the dictionary does not contain duplicate words.

For example, given

s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

// https://code.dennyzhang.com/word-break
// Basic Ideas:
// Complexity:
func wordBreak(s string, wordDict []string) bool {
    m := map[string]bool{}
    max_len := 0
    for _, word := range wordDict { 
        m[word] = true
        if len(word) > max_len { max_len = len(word) }
    }
    l := []int{0}
    status := false
    for i, _ := range s {
        status = false
        l2 := []int{}
        for _, j := range l {
            if i+1-j <= max_len {
                l2 = append(l2, j)
                str := s[j:i+1]
                if status == false && m[str] == true {
                    status = true
                    l2 = append(l2, i+1)
                }
            }
        }
        l = []int{}
        for _, j := range l2 { l = append(l, j) }
    }
    return status
}

Post Views: 4