給定一個字符串序列，檢查它是否匹配一個模式

Question

我在採訪中遇到了這個問題，我被困在最好的方式去了解它。問題如下：

給定一個字符串序列的單詞和一個字符串序列模式，如果單詞序列匹配模式，則返回true否則返回false。

match的定義：替換變量的單詞必須始終跟隨該替換。例如，如果「f」被替換爲「猴子」，那麼任何時候我們看到另一個「f」，那麼它必須匹配「猴子」，並且每當我們再次看到「猴子」時它就必須匹配「f」。

例子
輸入：「蟻狗貓的狗」，「一個dçd」
輸出：真
這是正確的，因爲每一個變量映射到只有一個字，反之亦然。
一個 - >蟻
d - >狗
Ç - >貓
d - >狗

輸入： 「螞蟻狗貓狗」， 「ADCE」
輸出：假
這是假，因爲如果我們用「d」替代「dog」，那麼你也不能將「e」替換爲「dog」。
一個 - >蟻
d，電子 - >狗（兩個d和e不能同時地圖到狗所以假）
Ç - >貓

輸入： 「猴子狗鰻魚鰻魚」，「 efcc「
輸出：真
這是真的，因爲每個變量都只映射到一個單詞而反之亦然。
ë - >猴
的F - >狗
Ç - >鰻魚

起初，我還以爲做的事情如下...

function matchPattern(pattern, stringToMatch) { 
    var patternBits = pattern.split(" "); 
    var stringBits = stringToMatch.split(" "); 
    var dict = {}; 

    if (patternBits.length < 0 
     || patternBits.length !== stringBits.length) { 
    return false; 
    } 

    for (var i = 0; i < patternBits.length; i++) { 
    if (dict.hasOwnProperty(patternBits[i])) { 
     if (dict[patternBits[i]] !== stringBits[i]) { 
     return false; 
     } 
    } else { 
     dict[patternBits[i]] = stringBits[i]; 
    } 
    } 
    return true; 
} 

var ifMatches = matchPattern("a e c d", "ant dog cat dog"); 
console.log("Pattern: " + (ifMatches ? "matches!" : "does not match!")); 

不過，我意識到這韓元」 t工作並且因爲它錯誤地返回true而使示例＃2失敗。解決此問題的一種方法是使用雙向字典或兩個字典，即存儲{「a」：「ant」}和 {「ant」：「a」}，並檢查if檢查中的兩種情況。但是，這似乎是浪費空間。有沒有更好的方法來解決這個問題，而不使用正則表達式？

Answer 1

我認爲一個簡單的選擇是單詞列表長度的二次方法是驗證列表索引的每個配對在兩個列表中具有相同的相等特性。我會假設你已經將「單詞」和「模式」列爲列表，並且不需要解析空格和其他內容 - 無論如何，這應該是一個單獨的函數的責任。

function matchesPatternReference(words, pattern) { 
    if(words.length !== pattern.length) return false; 
    for(var i = 0; i < words.length; i++) 
     for(var j = i+1; j < words.length; j++) 
      if((words[i] === words[j]) !== (pattern[i] === pattern[j])) 
       return false; 
    return true; 
} 

一個稍微好一點的方法是將兩個列表歸一化，然後比較歸一化的列表是否相等。要標準化列表，請將每個列表元素替換爲列表中首次出現之前出現的唯一列表元素的數量。如果您認爲哈希查找和列表附加需要一定的時間，這將在較長列表的長度上呈線性。我不知道有足夠的Javascript知道這些是否合理;當然，最糟糕的是，這個算法背後的思想可以在n * log（n）時間內用合適的數據結構來實現，即使不相信哈希查找是恆定時間的（這是一個有些可疑的假設，不管語言如何）。

function normalize(words) { 
    var next_id = 0; 
    var ids = {}; 
    var result = []; 
    for(var i = 0; i < words.length; i++) { 
     if(!ids.hasOwnProperty(words[i])) { 
      ids[words[i]] = next_id; 
      next_id += 1; 
     } 
     result.push(ids[words[i]]); 
    } 
    return result; 
} 

function matchesPatternFast(words, pattern) { 
    return normalize(words) === normalize(pattern); 
} 

注：正如在評論中指出，應該對數組檢查手動歸陣列的深平等，因爲===的確在Javascript的身份比較和不按元素進行比較。另請參閱How to check if two arrays are equal with Javascript?。

附錄：下面我認爲matchesPatternFast和matchesPatternReference計算相同的功能 - 但使用錯誤的假設該===陣列上進行比較的元素的逐點而不是一個指針比較。

我們可以定義以下功能：

function matchesPatternSlow(words, pattern) { 
    return matchesPatternReference(normalize(words), normalize(pattern)); 
} 

我觀察到normalize(x).length === x.length和normalize(x)[i] === normalize(x)[j]當且僅當x[i] === x[j];因此matchesPatternSlow計算與matchesPatternReference相同的功能。

我現在要說的是matchesPatternSlow(x,y) === matchesPatternFast(x,y)。當然，如果normalize(x) === normalize(y)那麼我們將擁有這個屬性。 matchesPatternFast將顯然返回true。另一方面，matchesPatternSlow通過在其兩個輸入上進行多次查詢並驗證這些查詢始終爲這兩個列表返回相同的結果：在循環外部，查詢爲function(x) { return x.length }，在循環內部，查詢爲function(x, i, j) { return x[i] === x[j]; }。由於相同的對象將對任何查詢作出相同的響應，因此兩個標準化列表上的所有查詢都將對齊，matchesPatternSlow也將返回true。

如果normalize(x) !== normalize(y)怎麼辦？那麼matchesPatternFast將明顯地返回false。但是，如果它們不相等，那麼它們的長度不匹配 - 在這種情況下，matchesPatternSlow也會按照我們所希望的matchesPatternReference中的第一個檢查返回false - 否則某些索引處的元素不相等。假設最小的不匹配指數是i。它是normalize的一個屬性，索引i上的元素將等於索引j<i上的元素，否則它將比索引0到i-1中的最大元素大一。所以我們現在有四個問題需要注意：

• 我們有j1<i和j2<i爲此normalize(x)[j1] === normalize(x)[i]和normalize(y)[j2] === normalize(y)[i]。但由於normalize(x)[i] !== normalize(y)[i]我們知道normalize(x)[j1] !== normalize(y)[i]。因此，當matchesPatternReference選擇指數j1和i時，我們會發現normalize(x)[j1] === normalize(x)[i]爲true和normalize(y)[j1] === normalize(y)[i]爲false，並立即返回false，正如我們試圖顯示的那樣。
• 我們有j<i其中normalize(x)[j] === normalize(x)[i]和normalize(y)[i]不等於normalize(y)的任何以前的元素。那麼matchesPatternReference將返回false當它選擇索引j和i時，因爲normalize(x)匹配在這些索引上，但normalize(y)沒有。
• 我們有j<i其中normalize(y)[j] === normalize(y)[i]和normalize(x)[i]不等於任何以前的元素normalize(x)。與之前的情況基本相同。
• 我們有normalize(x)[i]比normalize(x)和normalize(y)[i]的前面最大的元素大一個，比normalize(y)的最大元素大一個。但由於normalize(x)和normalize(y)就所有以前的元素達成一致，這意味着normalize(x)[i] === normalize(y)[i]，這與我們假設歸一化列表在此索引上不同的矛盾。

所以在所有的情況下，matchesPatternFast和matchesPatternSlow同意 - 因此matchesPatternFast和matchesPatternReference計算相同的功能。

Answer 2

對於這種特殊情況，我假設該模式是指匹配第一個字符。如果是這樣，你可以簡單地壓縮和比較。

# python2.7 

words = "ant dog cat dog" 
letters = "a d c d" 
letters2 = "a d c e" 

def match(ws, ls): 
    ws = ws.split() 
    ls = ls.split() 
    return all(w[0] == l for w, l in zip(ws + [[0]], ls + [0])) 

print match(words, letters) 
print match(words, letters2) 

有趣[[0]]和[0]到底是確保所述圖案和所述字具有相同的長度。