My recursive DFS solution got AC. We need more test cases.


  • 1
    J

    We should add two more test cases:

    dict = ["a","aa","ba"]
    s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
    
    dict = ["a","aa","ba"]
    s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabab"
    

    Code:

    class Solution {
    public:
        bool wordBreak(string s, unordered_set<string> &dict) {
            if (s.empty()) return false;
            // filter out useless words in the dictionary (pass the second test)
            unordered_set<string> words;
            unordered_set<int> lengths;  // cache of word lengths
            for (auto &word : dict) {
                if (s.find(word) != string::npos) {
                    words.insert(word);
                    lengths.insert(word.length());
                }
            }
            if (words.empty()) return false;
            // check if all characters can be found in the words (pass the first test)
            unordered_set<char> characters(s.begin(), s.end());
            for (char c : characters) {
                bool noMatchedWord = true;
                for (auto &word : words) {
                    if (word.find(c) != string::npos) {
                        noMatchedWord = false;
                        break;
                    }
                }
                if (noMatchedWord) return false;
            }
            return check(words, lengths, s, 0);
        }
        bool check(unordered_set<string> &dict, unordered_set<int> &lengths, string &s, int begin) {
            for (int length : lengths) {
                if (begin + length > s.length() ||
                        dict.find(s.substr(begin, length)) == dict.end()) {
                    continue;
                }
                if (begin + length == s.length() || check(dict, lengths, s, begin + length)) {
                    return true;
                }
            }
            return false;
        }
    };

  • 0

    I have added the two test cases you provided and your code TLE now. Thanks!


Log in to reply
 

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