leetcode 139. Word Break

Question

I am working on this question. It seems like that I have found the right answer and returns true but then it is overwritten by false.. Newbie in Java, sorry if it is a dummy question.. How do I just return true? Thank you in advance

Question Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given s = "leetcode", dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

import java.util.HashSet;
import java.util.Set;
public class Hi {

public static void main(String[] args) {
    String str = "leetcode";
    Set<String> set = new HashSet<String>();
    set.add("leet");
    set.add("code");
    boolean b = wordBreak(str, set);
    System.out.println("b is " + b);
}

public static boolean wordBreak(String s, Set<String> wordDict) {
    if(s.length() == 0 || wordDict.isEmpty()) {
        return false;
    }
    return helper(s, wordDict, 0);
}

public static boolean helper(String s, Set<String> wordDict, int index) {
    if(index == s.length()) {
        System.out.println("1 is called.. ");
        return true;
    }
    int curIndex = index;
    System.out.println("curIndex is " + curIndex);
    while(index < s.length()) {
        //System.out.println("s.length() is " + s.length());
        curIndex++;
        if(curIndex > s.length()) {
            System.out.println("2 is called.. ");
            //return false;
            return false;
        }
        if(wordDict.contains(s.substring(index, curIndex))) {
            System.out.println(s.substring(index, curIndex) + " curIndex is " + curIndex);
            helper(s, wordDict, curIndex);
        }
    }
    System.out.println("3 is called.. ");
    return false;
}

output: curIndex is 0

leet curIndex is 4

curIndex is 4

code curIndex is 8

1 is called..

2 is called..

b is false

@BrandonIbbotson You can just clicked the picture and it will be zoomed in. Thanks. — success

Sanjeev Dhiman Sanjeev Dhiman · Accepted Answer · 2016-09-07T23:01:49

This might not answer your question but I just mentioned an approach, and by no means I'm saying that my approach is better or more optimal.

In your code, there is no return true statement. The code does the right work but at the very end, since loop doesn't break anywhere, it always returns false. I mean you need to return true somewhere based on some condition and one of such conditions I mentioned in my below example.

private static boolean test(String str, Set<String> set) {
    int i = 1;
    int start = 0;
    List<String> tokens = new ArrayList<String>();

    while (i <= str.length()) {
        String substring = str.substring(start, i);
        if (set.contains(substring)) {
            tokens.add(substring);
            start = substring.length();
        }
        i++;
    }

    String abc = "";
    for (String a : tokens) {
        abc = abc + a;
    }

    System.out.println(abc);

    if (abc.equals(str)) {
        return true;
    } else {
        return false;
    }
}

Below is the screenshot from debug trace from within debugger.

leetcode 139. Word Break

1 Answers