优于网上博客:LeetCode 30. Substring with Concatenation of All Words 异常考虑更全面,使用hash性能优于红黑树的map


1:这题需要保存的是某个字符串需要出现几次,顺序并没有关系,所以unordered_map的hash实现性能要好于map的红黑树实现。
2:对于words和s为空的组合,标程报错,我的可以正常输出空值,哈哈。
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ans;
        if (s.size() == 0 || words.size() == 0){
            return ans;
        }
        
        unordered_map<string, int> hash, hashFind;
        int totalWord = words.size(), subLen = totalWord * words[0].size();
        
        for (int i = 0; i < words.size(); ++i){
            hash[words[i]]++;
        }
        
        for (int i = 0; i + subLen - 1 < s.size(); ++i){
            hashFind.clear();
            string str = s.substr(i, subLen);
            for (int j = 0; j + words[0].size() - 1 < str.size(); j += words[0].size()){
                string word = str.substr(j, words[0].size());
                hashFind[word]++;
            }
            if (hashFind == hash){
                ans.push_back(i);
            }
        }
        
        return ans;
    }
};
已邀请:

要回复问题请先登录注册

返回顶部