Leetcode-290-单词规律

题目描述

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

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

示例1:

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

示例 2:

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

示例 3:

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

示例 4:

输入: pattern = "abba", str = "dog dog dog dog"
输出: false
说明:
你可以假设 pattern 只包含小写字母， str 包含了由单个空格分隔的小写字母。

​

算法思路

• 在本题中，我们需要判断字符与字符串之间是否恰好一一对应。即任意一个字符都对应着唯一的字符串，任意一个字符串也只被唯一的一个字符对应。在集合论中，这种关系被称为「双射」。

• 想要解决本题，我们可以利用哈希表记录每一个字符对应的字符串，以及每一个字符串对应的字符。

• 然后我们枚举每一对字符与字符串的配对过程，不断更新哈希表，如果发生了冲突，则说明给定的输入不满足双射关系。

在实际代码中，我们枚举 pattern 中的每一个字符，利用双指针来均摊线性地找到该字符在 str 中对应的字符串。

每次确定一个字符与字符串的组合，我们就检查是否出现冲突，最后我们再检查两字符串是否比较完毕即可。

class Solution {
    public boolean wordPattern(String pattern, String s) {
        Map<String,Character> str2ch = new HashMap<>();         // 字符串映射字符
        Map<Character,String> ch2str = new HashMap<>();         // 字符映射字符串

        int m   = s.length();
        int idx = 0;                                            // idx 用于记录每个单词的开头位置

        // 枚举pattern中的每一个字符
        for(int p = 0;p < pattern.length();++p){
            char ch = pattern.charAt(p);                                // 枚举pattern中的每一个字符
            if(idx >= m){                                               // 说明字符和对应字符串的数量不匹配，直接返回false
                return false;
            }

            // 处理空格之间的字符串单词
            int j = idx;
            while(j < m && s.charAt(j) != ' '){                         // j用于记录每个字符串单词的结束位置
                j++;
            }
            String temp = s.substring(idx,j);                           // 拿出空格之间的这个单词

            // 离散数学：集合的双射匹配
            if(str2ch.containsKey(temp) && str2ch.get(temp) != ch){     // 字符串不匹配字符直接返回false
                return false;
            }
            if(ch2str.containsKey(ch) && !temp.equals(ch2str.get(ch))){ // 字符不匹配字符串直接返回false
                return false;
            }
            
            // 不在哈希表中 就加入到哈希表中 并且进入下一轮字符匹配
            str2ch.put(temp,ch);
            ch2str.put(ch,temp);
            idx = j + 1;            // 从下一个单词的开头进行匹配 
        }
        // 匹配到结束都满足条件（idx = j + 1）
        return idx > m;
    }
}

复杂度分析

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

打赏