Question

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

Answer 1

import Foundation

func wordBreak(_ s: String, _ dict: Set<String>) -> Bool {
    let slen = s.count
    var result = Array(repeating: false, count: slen + 1)
    result[0] = true // empty string is always segmentable

    let characters = Array(s)

    for i in 1...slen {
        for j in 0..<i {
            if result[j] {
                let substring = String(characters[j..<i])
                if dict.contains(substring) {
                    result[i] = true
                    break
                }
            }
        }
    }

    return result[slen]
}

let dict: Set<String> = ["future", "depends", "the", "on", "your", "dreams", "start", "today"]
let s = "futuredependsonyourdreams"

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



/*
run:

The string can be segmented

*/

 

70+ SQL courses for beginners and professionals

Answer 2

import Foundation

func isInDict(_ word: String, _ dict: [String]) -> Bool {
    return dict.contains(word)
}

func wordBreak(_ str: String, _ result: String, _ dict: [String]) {
    let strSize = str.count
    for i in 1...strSize {
        let subStr = String(str.prefix(i))
        if isInDict(subStr, dict) {
            if i == strSize {
                print(result + subStr)
                return
            }
            let remaining = String(str.dropFirst(i))
            wordBreak(remaining, result + subStr + " ", dict)
        }
    }
}

let str = "butterflyplaybasketballwithbags"
let dict = ["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