I have been working on code where I have to generate all possible ways to the target string. I am using the below-mentioned code.

Print Statement:

println("---------- How Construct -------")
    println("${
        window.howConstruct("purple", listOf(
            "purp",
            "p",
            "ur",
            "le",
            "purpl"
        ))
    }")

Function Call:

fun howConstruct(
        target: String,
        wordBank: List<String>,
    ): List<List<String>> {

        if (target.isEmpty()) return emptyList()

        var result = emptyList<List<String>>()

        for (word in wordBank) {
            if (target.indexOf(word) == 0) {    // Starting with prefix
                val substring = target.substring(word.length)
                val suffixWays = howConstruct(substring, wordBank)
                val targetWays = suffixWays.map { way ->
                    val a = way.toMutableList().apply {
                        add(word)
                    }
                    a.toList()
                }

                result = targetWays

            }
        }

        return result
    }

Expected Output:- [['purp','le'],['p','ur','p','le']]

Current Output:- []

CodePudding user response：

Your code is almost working; only a couple of small changes are needed to get the required output:

• If the target is empty, return listOf(emptyList()) instead of emptyList().
• Use add(0, word) instead of add(word).

The first of those changes is the important one. Your function returns a list of matches; and since each match is itself a list of strings, it returns a list of lists of strings. Once your code has matched the entire target and calls itself one last time, it returned an empty list — i.e. no matches — instead of a list containing an empty list — meaning one match with no remaining strings.

The second change simply fixes the order of strings within each match, which was reversed (because it appended the prefix after the returned suffix match).

However, there are many others ways that code could be improved. Rather than list them all individually, it's probably easier to give an alternative version:

fun howConstruct(target: String, wordBank: List<String>
    ): List<List<String>>
= if (target == "") listOf(emptyList())
else wordBank.filter{ target.endsWith(it) } // Look for suffixes of the target in the word bank
            .flatMap { suffix: String ->
                howConstruct(target.removeSuffix(suffix), wordBank) // For each, recurse to search the rest
                    .map{ it   suffix } } // And append the suffix to each match.

That does almost exactly the same as your code, except that it searches from the end of the string — matching suffixes — instead of from the beginning. The result is the same; the main benefit is that it's simpler to append a suffix string to a partial match list (using ) than to prepend a prefix (which is quite messy, as you found).

However, it's a lot more concise, mainly because it uses a functional style — in particular, it uses filter() to determine which words are valid suffixes, and flatMap() to collate the list of matches corresponding to each one recursively, as well as map() to append the suffix to each one (like your code does). That avoids all the business of looping over lists, creating lists, and adding to them. As a result, it doesn't need to deal with mutable lists or variables, avoiding some sources of confusion and error.

I've written it as an expression body (with = instead of { … }) for simplicity. I find that's simpler and clearer for short functions — this one is about the limit, though. It might fit as it an extension function on String, since it's effectively returning a transformation of the string, without any side-effects — though again, that tends to work best on short functions.

There are also several small tweaks. It's a bit simpler — and more efficient — to use startsWith() or endsWith() instead of indexOf(); removePrefix() or removeSuffix() is arguably slightly clearer than substring(); and I find == "" clearer than isEmpty().

(Also, the name howConstruct() doesn't really describe the result very well, but I haven't come up with anything better so far…)

Many of these changes are of course a matter of personal preference, and I'm sure other developers would write it in many other ways! But I hope this has given some ideas.