单词规律[简单]

╰半夏微凉° 2024-02-20 11:56 21阅读 0赞

> 优质博文：[IT-BLOG-CN][]

### 一、题目 ###

给定一种规律`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`中每个单词都被 单个空格 分隔

### 二、代码 ###

**思路：** 我们需要判断字符与字符串之间是否恰好一一对应。即任意一个字符都对应着唯一的字符串，任意一个字符串也只被唯一的一个字符对应。在集合论中，这种关系被称为「双射」。我们可以利用哈希表记录每一个字符对应的字符串，以及每一个字符串对应的字符。然后我们枚举每一对字符与字符串的配对过程，不断更新哈希表，如果发生了冲突，则说明给定的输入不满足双射关系。在实际代码中，我们枚举`pattern`中的每一个字符，利用双指针来均摊线性地找到该字符在`str`中对应的字符串。每次确定一个字符与字符串的组合，我们就检查是否出现冲突，最后我们再检查两字符串是否比较完毕即可。

class Solution {
        
        public boolean wordPattern(String pattern, String s) {
        
            if (pattern == null || s == null || pattern.length() == 0 || s.length() == 0) {
        
                return false;
            }
            // 创建2个Map，保存pattern中的字符为key，和s中的单词为vaule，另一个则相反。如果存在则进行比较，不存在则通过。
            Map<Character, String> p2s = new HashMap<>();
            Map<String, Character> s2p = new HashMap<>();
    
            String[] ss = s.split(" ");
            if (ss.length != pattern.length()) {
        
                return false;
            }
            for (int i = 0; i < ss.length; i++) {
        
                Character p = pattern.charAt(i);
                String si = ss[i];
                if ((p2s.containsKey(p) && !p2s.get(p).equals(ss[i])) || (s2p.containsKey(si) && !s2p.get(si).equals(p))) {
        
                    return false;
                }
                p2s.put(p, si);
                s2p.put(si, p);
            }
            return true;
        }
    }

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

[IT-BLOG-CN]: https://it-blog-cn.com/blogs/algorithm/topic/easy/word_patterns.html