290. Word Pattern

Leetcode

https://leetcode.com/problems/word-pattern/

題目

Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.

解答

• 方法一

var wordPattern = function(pattern, s) {
    const arr = s.split(' ');
    if(pattern.length !== arr.length) return false;
    
    const map1 = {};
    const map2 = {};
    for(let i=0; i<pattern.length; i++) {
        const value1 = pattern[i];
        const value2 = arr[i];
        if(map1[value1] || map2[value2]) {
            if(map1[value1] !== value2) return false;
            if(map2[value2] !== value1) return false;
        } else {
            map1[value1] = value2;
            map2[value2] = value1;
        }
    }
    return true;
};

Runtime: 76 ms, faster than 61.17% of JavaScript online submissions for Word Pattern.

Memory Usage: 38.7 MB, less than 39.56% of JavaScript online submissions for Word Pattern.

• 方法二

用 map 實作

var wordPattern = function(pattern, s) {
    const arr = s.split(' ');
    if(pattern.length !== arr.length) return false;
    
    const map1 = new Map();
    const map2 = new Map();
    for(let i=0; i<pattern.length; i++) {
        const value1 = arr[i];
        const value2 = pattern[i];
        if(map1.has(value2) || map2.has(value1)) {
            if(map1.get(value2) !== value1) return false;
            if(map2.get(value1) !== value2) return false;
        } else {
            map1.set(value2, value1);
            map2.set(value1, value2);
        }
    }
    return true;
};

Runtime: 108 ms, faster than 20.15% of JavaScript online submissions for Word Pattern.

Memory Usage: 38.1 MB, less than 87.30% of JavaScript online submissions for Word Pattern.

測資

let pattern = "abba", s = "dog cat cat dog";

console.log(wordPattern(pattern, s));