The same Solution in C++ and Java,why the former TLE and the latter AC?


  • 0
    C
    class Solution {
    public:
        vector<int> findSubstring(string S, vector<string> &L) {
            vector<int> res;
            int len = L.size();
            if(len == 0)
                return res;
            int size = L[0].size();
            if(size == 0 || S.size() < len * size)
                return res;
            unordered_map<string,int> gold_count;
            for(int i = 0;i < L.size(); ++ i){
                if(gold_count.find(L[i]) == gold_count.end())
                    gold_count[L[i]] = 0;
                gold_count[L[i]] += 1;
            }
            
            for(int i = 0;i <= S.size() - len * size; ++ i){
                unordered_map<string,int> count(gold_count);
                for(int j = i;j < i + len * size;j += size){
                    string s = S.substr(j,size);
                    unordered_map<string,int>::iterator it = gold_count.find(s);
                    if(it == gold_count.end())
                        break;
                    int v = it -> second;
                    if(v == 1)  gold_count.erase(it);
                    else    gold_count[s] -= 1;
                }
                if(gold_count.empty())
                    res.push_back(i);
                gold_count = count;
            }
            return res;
        }
    };
    
    import java.util.Hashtable;
    public class Solution {
        public ArrayList<Integer> findSubstring(String S, String[] L) {
            // Note: The Solution object is instantiated only once and is reused by each test case.
            ArrayList<Integer> result = new ArrayList<Integer> ();
            if(L.length == 0) return result;
            if(L[0].length() == 0) return result;
            if(S == null ||S.length() <L[0].length()*L.length) return result;
            Hashtable<String,Integer> ht = new Hashtable<String,Integer>();
            for(int i=0;i<L.length;i++)
            	if(ht.containsKey(L[i]))
            		ht.put(L[i], ht.get(L[i])+1);
            	else
            		ht.put(L[i], 1);//防止L中有重复的值。
            for(int j = 0;j<=S.length()-L[0].length()*L.length;j++){
            	Hashtable<String,Integer> htt = new Hashtable<String,Integer>(ht);
            	for(int i = j;i < j+L[0].length()*L.length; i += L[0].length()){
            		String ss = S.substring(i,i+L[0].length());
            		if(ht.containsKey(ss)){
            			int value = ht.get(ss);
            			if(value == 1) ht.remove(ss);
            			else ht.put(ss, value-1);
            		}
            		else break;
            	}
            	if(ht.size() == 0) result.add(j);
            	ht = htt;
            }
    		return result;
        }
    }

  • 0
    R

    Because in the beginning of every loop you create a map and in the end you copy a map.
    What's more, since you already have an iterator, why use gold_count[s], it does the search again


Log in to reply
 

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