Need add more test case to "Word Break"


  • 3
    C

    I have a solution that could pass all the test cases, but turned out to be a wrong answer.

    Here was the solution.
    The idea is to solve the problem recursively, check all the sub-string but longer one first (which may save time)
    General steps are:

    1. lenSub from len to 1
    2. divide the string into two parts, if the first part is in dict, recursively check the second part

    The problem of the first solution is that when the second part is not breakable, it stops check.

    
    class Solution {
    public:
        bool wordBreak(string s, unordered_set<string> &dict) {
            int len = s.length();
            if (len == 0) {
                return true;
            }
            
            for (int lenSub = len; lenSub > 0; lenSub--) {
                string strSub = s.substr(0, lenSub); // 0 to lenSub-1
                string strLeft = s.substr(lenSub, len - lenSub); // lenSub to len - 1
                if (dict.find(strSub) != dict.end()) {
                    return wordBreak(strLeft, dict);
                }
            }
            
            return false;
        }
    };
    

    Actually the correct one should be

    
    class Solution {
    public:
        bool wordBreak(string s, unordered_set<string> &dict) {
            int len = s.length();
            if (len == 0) {
                return true;
            }
    
            for (int lenSub = len; lenSub > 0; lenSub--) {
                string strSub = s.substr(0, lenSub); // 0 to lenSub-1
                string strLeft = s.substr(lenSub, len - lenSub); // lenSub to len - 1
                if (dict.find(strSub) != dict.end()) {
                    if (wordBreak(strLeft, dict)) {
                        return true;
                    }
                    
                }
            }
            
            return false;
        }
    };
    

    Which is actually not efficient enough to pass all the cases.

    So I'd suggest add test case like:
    "cars", ["car","ca", "rs"]


  • 0
    S

    Could you please correct your code format? Select all code then click {} button. One more thing, could you please add some words about the algorithm of 2 solution, and why it happends. Thanks.


  • 0

    Thanks, Cheney! I have added your test case to this problem.


  • 0
    C

    Changed accordingly, let me know if you have further questions, sorry for the delay.


  • 0
    H

    I did similar code but get TLE.


  • 0
    C

    Yes, this solution must get TLE. 1st, it has done a lot of redundant checking; 2, at each recursive round, it regenerate a new substring by calling s.substr(), which is expensive.


  • 0
    R

    For avoiding from TLE we can use map, that we can ignore substrings those were generated before.
    My Accepted Java Code:
    HashMap<String, Integer> map = new HashMap<>();

    public boolean wordBreak(String s, Set<String> dict) {
        int len = s.length();
        if (s.length() == 0 || dict.contains(s)) {
            return true;
        }
        for (int i = 0; i < len; i++) {
            String subString1 = s.substring(0, i);
            String subString2 = s.substring(i, len);
            //System.out.println(subString1 + " " + subString2);
            if (dict.contains(subString1)) {
                if (map.get(subString2) == null) {
                    map.put(subString2,1);
                    if (wordBreak(subString2, dict)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

Log in to reply
 

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