Can anyone help to explain why the following case expected True? How "bb" segmented?


  • 0
    H

    Submission Result: Wrong Answer

    Input: "bb", ["a","b","bbb","bbbb"]
    Output: false
    Expected: true


  • 0
    F

    you dict have a word "b", so that the input string "bb" can be segmented to "b b" so it should be true.

    here is my AC solution with HashMap:

        public class Solution {
                public boolean wordBreak(String s, Set<String> dict) {
                    HashMap<Integer, Boolean> hmap=new HashMap<Integer, Boolean>();
                    return wordBreakRec(s,dict,0, hmap);
                }
        
                public boolean wordBreakRec(String s, Set<String> dict, int index, HashMap<Integer, Boolean> map)         {
                    if(index>=s.length()) return true;
                    if(map.get(index)!=null){  //  we knew whether substring(index, length) is breakable
                        return map.get(index);
                    }
                    for(int i=index+1; i<=s.length(); i++){
                        if(dict.contains(s.substring(index,i))){
                            if( wordBreakRec(s, dict, i, map)){
                                 map.put(i,true);   //substring(index, length) is a sub-optimal solution, store the result
                                 return true; 
                            }
                            else{
                                map.put(i,false); //substring(index, length) is not breakable, store the result
                            }
                        }
                    }
                    return false;
                } 
       }

  • 0
    H

    @facetothefate,

    Thanks a lot for your explanation and AC code.
    I get it and I think the description of the problem is not accurate.
    There is no mention about the string in the array can be reused.
    :-)
    Thanks and Best Regards,
    Yaoyu


  • 0
    H
    This post is deleted!

  • 0
    H
    This post is deleted!

  • 0
    H
    This post is deleted!

  • 0

    @heyaoyu i agree. i stumbled on the same issue


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.