Recursive program printing but not returning correct values

Question

I'm trying to solve a leetcode problem called word break https://leetcode.com/problems/word-break/

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.

I'm able to print the different word breaks that fit the solution but when returning my code always returns None. How can I fix it so that res is an array containing the different words in the dictionary that create s

import sys; 

class Solution:
    def wordBreak(self, s, wordDict):
        res = self.driver(s, 0, len(s), wordDict, [])
        print(res)

    def driver(self, text, start, end, wordDict, res):
        if text[start:end] == None:    
            return res
        elif text[start:end] in wordDict:
            result = text[start:end]
            res.append(result)
            print(res)
            return self.driver(text, end, len(text), wordDict, res)
        else:
            for i in range(start, end):
                self.driver(text, start, i, wordDict, res)

Why do you even need a class for this? As a side note, driver does not return anything in the recursive case. — DYZ
– DYZ, Commented Jan 8, 2019 at 1:55
@DYZ I think that website expects solutions in a class Solution for their code challenges — Charles Landau
– Charles Landau, Commented Jan 8, 2019 at 2:02

cdlane · Accepted Answer · 2019-01-08 08:04:57Z

As is common with recursive problems like this, you're making it harder than necessary by not letting the recursion do the work. Although the solution by @blhsing is elegant (+1), let's work with your design, but simplify it:

class Solution:
    def wordBreak(self, s, wordDict):
        return self.wordBreak_recursive(s, 0, len(s), wordDict)

    def wordBreak_recursive(self, s, start, end, wordDict):

        for index in range(start + 1, end + 1):
            if s[start:index] in wordDict and (index == end or self.wordBreak_recursive(s, index, end, wordDict)):
                return True

        return False

There is no need to collect the segments in res as the requirement is a boolean result as to whether the fitting is possible or not:

solver = Solution()

print(solver.wordBreak("leetcode", ["leet", "code"]))
print(solver.wordBreak("applepenapple", ["apple", "pen"]))
print(solver.wordBreak("catsandog", ["cats", "dog", "sand", "and", "cat"]))

OUTPUT

> python3 test.py
True
True
False
>

Similarly, we don't need to find all solutions, just one to qualify.

Finally, If your recursive method returns a value, then any time we call it recursively, we generally need to address that returned value, not ignore it -- even if the recursive method secures a result by modifying a variable in its caller's environment. Otherwise, perhaps it shouldn't return anything.

blhsing · Accepted Answer · 2019-01-08 17:18:54Z

1

You can check if the given string s starts with any word in the wordDict, and then recursively check if the rest of the string in s can be partitioned with words in wordDict:

class Solution:
    def wordBreak(self, s, wordDict):
        return not s or any(s.startswith(word) and self.wordBreak(s[len(word):], wordDict) for word in wordDict)

edited Jan 8, 2019 at 17:18

answered Jan 8, 2019 at 1:59

blhsing

109k9 gold badges88 silver badges132 bronze badges

2 Comments

cdlane Over a year ago

There's a subtlety here in that the problem states that wordBreak will be "Given a non-empty string" but your solution relies on it being given an empty string to terminate the recursion and return True. I'm not sure how to to think about that contradiction, but an elegant solution nonetheless (+1).

blhsing Over a year ago

Thanks. Since the behavior of the function when given an empty s is undefined by the question, I believe that we have the freedom to make it return what's convenient when s is empty. Note that I've also simplified the code to make it less verbose.

Collectives™ on Stack Overflow

Recursive program printing but not returning correct values

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related