Leetcode 单词规律

即判断给定的模式字符串（pattern）和单词字符串（s）是否遵循相同的对应规则。具体来说，就是要判断 pattern 中的字符与 s 中的单词是否存在一一对应的关系，即双射（bijection）。

算法思想：

1. 输入解析：

   • 将字符串 s 按照空格分割成一个单词数组（words），因为 s 是由空格分隔的单词组成。
   • 如果 pattern 的长度和单词数组的长度不相等，直接返回 false。因为字符和单词的数量必须一致，否则无法形成一一对应的关系。

2. 使用两个哈希表：

   • 使用两个哈希表（HashMap）来分别记录字符到单词的映射和单词到字符的映射。
     • charToWord 用于存储模式字符串中的字符与单词的对应关系。
     • wordToChar 用于存储单词与模式字符的对应关系。

3. 遍历模式字符串和单词数组：

   • 对模式字符串的每个字符和对应的单词进行遍历。
   • 如果字符 c 已经在 charToWord 中有映射关系：
     • 检查其映射的单词是否与当前单词一致。如果不一致，返回 false。
   • 如果字符 c 没有映射关系：
     • 检查当前单词是否已经被映射到某个字符。如果已经被映射，返回 false。
     • 如果没有被映射，则建立字符与单词的双向映射关系，将字符和单词互相映射。

4. 一致性检查：

   • 遍历完所有字符和单词后，如果所有映射关系都满足规则，则返回 true，否则返回 false。

具体步骤的中文解释：

1. 首先将字符串 s 分割成单词数组 words，并检查 pattern 和 words 的长度是否相等。如果长度不相等，则无法匹配，直接返回 false。
2. 使用两个哈希表：
   • charToWord 用于存储 pattern 中的每个字符到 words 中对应单词的映射关系。
   • wordToChar 用于存储 words 中的每个单词到 pattern 中对应字符的映射关系。
3. 遍历 pattern 中的每个字符及其对应的单词：
   • 如果当前字符已经在 charToWord 中有映射关系，但映射的单词与当前单词不一致，则返回 false。
   • 如果当前单词已经在 wordToChar 中有映射关系，但映射的字符与当前字符不一致，也返回 false。
   • 如果不存在不一致的情况，则建立字符与单词的双向映射关系。
4. 如果所有字符和单词都成功建立了双向映射，并且没有冲突，则返回 true。

代码的时间复杂度：

• 时间复杂度为 O(n)，其中 n 为模式字符串的长度或单词数组的长度。每个字符和单词的映射操作都是常数时间的哈希表查找操作，所以整体复杂度为线性。

通过双向映射保证了字符和单词之间的双射关系，可以确保模式与字符串的对应关系是唯一且一致的。

java 实现

class Solution {
    public boolean wordPattern(String pattern, String s) {
        //先分割单词,根据长度是否相等进行初步判断
        String[] words = s.split(" ");
        if(words.length != pattern.length()) {
            return false;
        }
        Map<Character, String> charToWord = new HashMap<>();
        Map<String, Character> WordToChar = new HashMap<>();
        for(int i = 0; i < pattern.length(); ++i) {
            String word = words[i];
            if(charToWord.containsKey(pattern.charAt(i))) {
                if(!charToWord.get(pattern.charAt(i)).equals(word)) {
                    return false;
                }
            }else {
                //之所以可以通过这一部分的代码片段进行结果判断，是因为charToWord和wordToChar是同时更新的
                if(WordToChar.containsKey(word)) {
                    return false;
                }
                charToWord.put(pattern.charAt(i), word);
                WordToChar.put(word, pattern.charAt(i));
            }
        }
        return true;
    }
}