leetcode word Pattern javascript的O(n)和O(n2)两种不同解法用的时间一样?

kukuv2
  • 1.1k

题目地址word Pattern
第一种O(n2)解法,我一开始想出的笨方法。

var wordPattern = function(pattern, str) {
    var patternArray = pattern.split("");
    var strArray = str.split(" ");
    var result = true;
    if (patternArray.length !== strArray.length) {
        return false;
    }
    patternArray.forEach(function(curValue, index, arr) {
        var currIndex = index;
        for (; index > 0; index--) {
            if (curValue === arr[index - 1]) {
                if (strArray[currIndex] !== strArray[index - 1]) {
                    result = false;
                }
            } else {
                if (strArray[currIndex] === strArray[index - 1]) {
                    result = false;
                }
            }
        }
    }
    );
    return result;

}

第二种O(n)解法

var wordPattern = function(pattern, str) {
    var strArray = str.split(" ");
    var hash = {};
    var hash1 = {};
    if(pattern.length !== strArray.length){
        return false;
    }
    for(var i=0;i<pattern.length;i++){
        var item = pattern.charAt(i);
        var strItem = strArray[i];
        if(hash[item]){
            if(!hash1[strItem]) return false;
            hash[item] = false;
            hash1[strItem] = false;
        }else{
            if(hash1[strItem]) return false;
            hash[item] = true;
            hash1[strItem] = true;
        }
    }
    return true;
    
};

两种解法消耗的时间既然一样、、、

clipboard.png
有人能解答下吗?

回复
阅读 2.7k
1 个回答

时间瓶颈可能不在你算法上

你知道吗?

宣传栏