Same input & code, leetcode returns differently. (Word break problem)


  • 2
    H

    With the same code

    public class Solution {

    Iterator<String> curItr = null;
    Iterator<String> lastItr = null;
    public boolean wordBreak(String s, Set<String> wordDict)
    {
        if (wordDict == null || wordDict.size() == 0)
            return false;
    
        if (s.length() == 0 || s.equals(""))
            return true;
        
        if (curItr == null)
            curItr = wordDict.iterator();
        
        if (curItr.hasNext())
        {
            String cur = curItr.next();
            if (!curItr.hasNext())
                return s.equals(cur);
    
            int b = s.indexOf(cur);
            if (b >= 0)
            {
                String[] s1 = s.split(cur, 2);
                lastItr = curItr;
                for (String str : s1)
                {
                    curItr = wordDict.iterator();//reset iterator
                    if (!wordBreak(str, wordDict))
                    {
                        curItr = lastItr;
                        return wordBreak(s, wordDict);
                    }
                }
                return true;
            }
            else
                return wordBreak(s, wordDict);
        }
        else
        {
            return false;
        }
    }
    

    }

    and input:
    "bccdbacdbdacddabbaaaadababadad", ["cbc","bcda","adb","ddca","bad","bbb","dad","dac","ba","aa","bd","abab","bb","dbda","cb","caccc","d","dd","aadb","cc","b","bcc","bcd","cd","cbca","bbd","ddd","dabb","ab","acd","a","bbcc","cdcbd","cada","dbca","ac","abacd","cba","cdb","dbac","aada","cdcda","cdc","dbc","dbcb","bdb","ddbdd","cadaa","ddbc","babb"]

    Leetcode returns a false, but my java 1.6 returns true.
    Can anyone help me out?
    Thanks!


  • 0
    K

    Even on my Java 1.7 facing this problem with the same input (but a different implementation than the one above)


  • 0
    A

    yessssssssssssss


  • 0

    I have added several smaller test cases which should help you to debug. Try these test cases:

    "ccbb", ["bc","cb"]
    "cbca", ["bc","ca"]
    "ccaccc", ["cc","ac"]
    "acccbccb", ["cc","bc","ac","ca"]
    "ccacccbcab", ["cc","bb","aa","bc","ac","ca","ba","cb"]

Log in to reply
 

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