Question

How to check whether a string can be segmented into a sequence of words from a dictionary in Go

Answer 1

package main

import (
    "fmt"
)

func wordBreak(s string, dict map[string]bool) bool {
    slen := len(s)
    result := make([]bool, slen+1)
    result[0] = true // empty string is always segmentable

    for i := 1; i <= slen; i++ {
        for j := 0; j < i; j++ {
            if result[j] && dict[s[j:i]] {
                result[i] = true
                break
            }
        }
    }

    return result[slen]
}

func main() {
    dict := map[string]bool{
        "future":  true,
        "depends": true,
        "the":     true,
        "on":      true,
        "your":    true,
        "dreams":  true,
        "start":   true,
        "today":   true,
    }

    s := "futuredependsonyourdreams"

    if wordBreak(s, dict) {
        fmt.Println("The string can be segmented")
    } else {
        fmt.Println("The string cannot be segmented")
    }
}



/*
run:

The string can be segmented

*/

 

70+ SQL courses for beginners and professionals

Answer 2

package main

import (
    "fmt"
)

func isInDict(word string, dict []string) bool {
    for _, w := range dict {
        if w == word {
            return true
        }
    }
    
    return false
}

func wordBreak(str string, result string, dict []string) {
    strsize := len(str)
    for i := 1; i <= strsize; i++ {
        subStr := str[:i]

        if isInDict(subStr, dict) {
            if i == strsize {
                result += subStr
                fmt.Println(result)
                return
            }
            wordBreak(str[i:], result+subStr+" ", dict)
        }
    }
}

func main() {
    str := "butterflyplaybasketballwithbags"
    dict := []string{
        "butterfly", "basketball", "bagpiper", "and", "play",
        "with", "butter", "fly", "basket", "ball", "bags",
    }

    wordBreak(str, "", dict)
}



/*
run:

butter fly play basket ball with bags
butter fly play basketball with bags
butterfly play basket ball with bags
butterfly play basketball with bags

*/

 

70+ SQL courses for beginners and professionals