Why did my C++ code got TLE but the Java version was accepted and beat 92.94%?


  • 0
    L
    //C++
    class Solution {
    public:
        bool wordBreak(string s, unordered_set<string>& wordDict) {
            unordered_map<string, bool> m;
            m[""] = true;
            return f(s, wordDict, m);
        }    
        bool f(string s, unordered_set<string> wordDict, unordered_map<string, bool> m){
            if (m.find(s) != m.end()) return m[s];
            for (int i = s.size(); i >= 1; i--){
                if (wordDict.find(s.substr(0, i)) != wordDict.end()){
                    string right = s.substr(i, s.size() - i);
                    bool t = f(right, wordDict, m);
                    if(t){
                        m[right] = true;
                        return true;
                    }
                }
            }
            m[s] = false;
            return false;
        }
    };
    
    //Java
    public class Solution {
        public boolean wordBreak(String s, Set<String> wordDict) {
            HashMap<String, Boolean> m = new HashMap<String, Boolean>();
            m.put("", true);
            return f(s, wordDict, m);
        }    
        public Boolean f(String s, Set<String> wordDict, HashMap<String, Boolean> m){
            if (m.containsKey(s)) return m.get(s);
            for (int i = s.length(); i >= 1; i--){
                if (wordDict.contains(s.substring(0, i))){
                    String right = s.substring(i);
                    Boolean t = f(right, wordDict, m);
                    if(t){
                        m.put(right, true);
                        return true;
                    }
                }
            }
            m.put(s, false);
            return false;
        }
    }

Log in to reply
 

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