Word Break Problem: Not getting the expected O/P for the negative cases

Question

I have written a code using java on word break problem. This idea is to return the list of words from the dictionary which when combined give the entered string. I have used TRIE data structure in my approach. It is working fine for positive cases, however, it is not working as expected for negative cases.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class WordBreakProblem {

    public class Node{

        String prefix;
        Map<Character, Node> children;
        boolean isWord;

        public Node(String prefix){
            this.prefix = prefix;
            children = new HashMap<Character, Node>();
            isWord = false;
        }
    }

    Node trie;
    public WordBreakProblem(String[] words){
        trie = new Node("");
        for(String s : words){
            insertIntoTrie(s);
        }

    }

    private void insertIntoTrie(String s) {
        Node curr = trie;
        for(int i=0; i<s.length(); i++){
            if(!curr.children.containsKey(s.charAt(i)))
                curr.children.put(s.charAt(i), new Node(s.substring(0, i+1)));
            curr = curr.children.get(s.charAt(i));
            if(i == s.length()-1)
                curr.isWord = true;
        }

    }

    public ArrayList<String> searchForPair(String str, ArrayList<String> list){
        Node curr = trie;
        int i;
        for(i = 0; i<str.length(); i++){
            if(curr.children.containsKey(str.charAt(i))){
                curr = curr.children.get(str.charAt(i));
            }
            else
                break;
        }
        if(curr.isWord){
            list.add(curr.prefix);
            searchForPair(str.substring(i), list);
        }
        else
            return null;

        return list;
    }

    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<String>();
        WordBreakProblem w = new WordBreakProblem(new String[]{"news", "abcd", "tree", "geeks", "paper"});
        List<String> al = w.searchForPair("newsgeeksabc", list);
        for(String s : al){
            System.out.println(s);
        }
    }
}

Expected: null

Output:

news

geeks

Since "abc" is not present in the dictionary, it should return null.

The problem seems to be somewhere here:

if(curr.isWord){
            list.add(curr.prefix);
            searchForPair(str.substring(i), list);
        }
        else
                   return null;

[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173) — Andy Turner, May 19 '19 at 19:14

Andy Turner · Answer 1 · 2019-05-19T19:41:05.707

0

It's a little hard to follow your code, as I am not entirely sure why you expect it to return null. From what I can glean, you expect it to return null because you come across something that isn't a word - so, despite finding words previously, you want to throw those away and return null.

It's because you ignore the return value in your recursive call:

    if(curr.isWord){
        list.add(curr.prefix);
        searchForPair(str.substring(i), list);  // HERE
    }
    else
               return null;

    return list;

Even if that recursive call returns null, you ignore it and still return list.

Handle the case of receiving null:

if (curr.isWords) {
  list.add(curr.prefix);
  List<String> result = searchForPair(str.substring(i), list);
  if (result == null) {
    return null;
  }
} else {
  return null;
}
return list;

If I may offer a couple of observations on the code:

return/break in an else is a sign that your code code be made clearer (you may find it clearer) if you invert the condition, and remove the else, for example:
```
if(!curr.isWord){
  return null;
}
list.add(curr.prefix);
searchForPair(str.substring(i), list);  // HERE
return list;
```
Returning null is awkward in the case of not finding any words, because calling code then has to handle the case that it's null. The API may be easier to use if you return some non-null value to represent "no words found", such as an empty list.

edited May 19 '19 at 19:41

answered May 19 '19 at 19:34

Andy Turner

137,514
11
162
243

I agree on your comment about using null. However, in some cases, I prefer to return null. For example, if I use a library that does mathematical operations on some physical observation, the library returns null if something goes very wrong. In that case, it comes compatible that I return null as well, if I'm intending to extend functionality of that library. What is your take on this? Do you think returning null for these types of things is applicable or not? – May 19 '19 at 19:52
@Maximus if something goes very wrong, throw an exception. That's what they are for. – Andy Turner May 19 '19 at 21:46
Well, maybe in Java and C++ yes. But even then, code above has to handle the exception, just like it has to handle null. (Though exceptions make it much more clear on how to handle what). However, for people coming from C background, or for people whom use C with C++ and/or Java (as in jni) together, returning null makes readability much more coherent, because math/physics libraries written originally in C and then ported to other languages almost always return null for a successful run that does not produce any output. – May 19 '19 at 22:04
It also makes more sense to check if the output is null, rather than to check if it's size is less then some magic number. By checking for null, you'll essentially be checking for empty output. By checking size (or any other check for that matter), you'll have to read the rest of the code to understand what's going on. But if you just check for nulls religiously, it would mean to the reader that there's a math problem, it shouldn't be happening so just wing it and leave the function. – May 19 '19 at 22:07
As for exceptions, I believe it is best to leave them to exceptional situations. Throwing an exception for every possible null outcome of a code? I don't know, maybe put some nulls and throw an exception for a collection of nulls? Maybe that'll be better. But that's just how I prefer, perhaps industry does it otherwise. – May 19 '19 at 22:10
@Maximus you said "if something goes very wrong": this sounds rather like an exceptional situation. If it is an expected outcome, that's not going *wrong*: in such a situation, returning, say, `OptionalDouble`, is preferable to null. – Andy Turner May 20 '19 at 05:26
@AndyTurner You got it right regarding what i want from this code (if there is no matching word from the dictionary, flush the list and return null). However, from the below code, i doubt if i am achieving so. `List result = searchForPair(str.substring(i), list); if (result == null) { return null; } } else { return null;` Since, here result is storing the previously matched words. And this code still returns the 2 matched words though the third words is not found in the dictionary. – Aman May 20 '19 at 06:38
@AndyTurner My bad. Never seen `OptionalDouble` used before on libraries such as OpenCV etc. but it is a good idea! Perhaps much better than null for some cases. – May 20 '19 at 12:16

Word Break Problem: Not getting the expected O/P for the negative cases

1 Answers1