Question

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

Answer 1

fun wordBreak(s: String, dict: Set<String>): Boolean {
    val slen = s.length
    val result = BooleanArray(slen + 1) { false }
    result[0] = true // empty string is always segmentable

    for (i in 1..slen) {
        for (j in 0 until i) {
            if (result[j] && dict.contains(s.substring(j, i))) {
                result[i] = true
                break
            }
        }
    }

    return result[slen]
}

fun main() {
    val dict = setOf("future", "depends", "the", "on", "your", "dreams", "start", "today")
    val s = "futuredependsonyourdreams"

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



/*
run:

The string can be segmented

*/

 

70+ SQL courses for beginners and professionals

Answer 2

fun isInDict(word: String, dict: List<String>): Boolean {
    return dict.contains(word)
}

fun wordBreak(str: String, result: String, dict: List<String>) {
    val strSize = str.length
    for (i in 1..strSize) {
        val subStr = str.substring(0, i)
        if (isInDict(subStr, dict)) {
            if (i == strSize) {
                println(result + subStr)
                return
            }
            wordBreak(str.substring(i), result + subStr + " ", dict)
        }
    }
}

fun main() {
    val str = "butterflyplaybasketballwithbags"
    val dict = listOf(
        "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