41.单词规律

题目

给定一种规律pattern和一个字符串s，判断s是否遵循相同的规律。

这里的遵循指完全匹配，例如，pattern里的每个字母和字符串s中的每个非空单词之间存在着双向连接的对应规律。

示例1:

输入: pattern = "abba", s = "dog cat cat dog"
输出: true

示例 2:

输入:pattern = "abba", s = "dog cat cat fish"
输出: false

示例 3:

输入: pattern = "aaaa", s = "dog cat cat dog"
输出: false

提示:

1 <= pattern.length <= 300
pattern 只包含小写英文字母
1 <= s.length <= 3000
s 只包含小写英文字母和 ' '
s 不包含任何前导或尾随对空格
s 中每个单词都被单个空格分隔

思路

和上一题的思路完全一样，由字符之间的一一映射升级成了字符与字符串之间的一一映射。首先本质是一样的，要实现一一映射，就要用到两个哈希表分别记录字符到字符串的映射和字符串到字符的映射。其次，我们要对s中的单词进行提取，比较单词数量和pattern中的数量是否一致，如果数量上不一致，二者一定不匹配；

class Solution {
    fun wordPattern(pattern: String, s: String): Boolean {
        val split = s.split(" ")
        if (pattern.length != split.size) {
            return false
        }
        val p2sHash = HashMap<Char, String>()
        val s2pHash = HashMap<String, Char>()

        for (i in pattern.indices) {
            if (p2sHash.containsKey(pattern[i])) {
                if (p2sHash[pattern[i]] != split[i]) {
                    return false
                }
            } else {
                p2sHash[pattern[i]] = split[i]
            }

            if (s2pHash.containsKey(split[i])) {
                if (s2pHash[split[i]] != pattern[i]) {
                    return false
                }
            } else {
                s2pHash[split[i]] = pattern[i]
            }
        }

        return true
    }
}


class Solution {
    public boolean wordPattern(String pattern, String s) {
        Map<Character, String> p2s = new HashMap<>();   // pattern中的字符到s中的字符子串的映射表
        Map<String, Character> s2p = new HashMap<>();   // s中的字符字串到pattern中的字符的映射表
        String[] words = s.split(" ");                  // 根据空格，提取s中的单词
        int n = pattern.length();
        int m = words.length;
        if(n != m){
            return false;   // 字符数和单词数不一致，一定不匹配
        }
        char ch;
        String word;
        for(int i = 0; i < n; i++){
            ch = pattern.charAt(i);
            word = words[i];
            if((p2s.containsKey(ch) && !p2s.get(ch).equals(word)) || (s2p.containsKey(word) && s2p.get(word) != ch)){
                // 字符与单词没有一一映射：即字符记录的映射不是当前单词或单词记录的映射不是当前字符
                return false;
            }
            // 更新映射，已存在的映射更新后仍然是不变的；不存在的映射将被加入
            p2s.put(ch, word);
            s2p.put(word, ch);
        }
        return true;
    }
}


class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        words = s.split(' ')
        length = len(words)
        if length != len(pattern):
            return False

        p2s = {}
        s2p = {}

        for i in range(length):
            word = words[i]
            p = pattern[i]

            if (word in s2p and s2p[word] != p) or (p in p2s and p2s[p] != word):
                return False

            p2s[p] = word
            s2p[word] = p

        return True

复杂度分析:

时间复杂度：O(n+m)，其中 n 为 pattern 的长度，m 为 str 的长度。插入和查询哈希表的均摊时间复杂度均为 O(n+m)。每一个字符至多只被遍历一次。
空间复杂度：O(n+m)，其中 n 为 pattern 的长度，m 为 str 的长度。最坏情况下，我们需要存储 pattern 中的每一个字符和 str 中的每一个字符串。

下一题

邮箱：charon.chui@gmail.com
Good Luck!