算法-Hash-单词规律

淡淡的烟草味﹌ 2023-03-13 03:18 14阅读 0赞

# 算法-Hash-单词规律 #

# 1 题目概述 #

## 1.1 题目出处 ##

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

## 1.2 题目描述 ##

给定一种规律 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 包含了由单个空格分隔的小写字母。

# 2 HashMap #

# 2.1 思路 #

1.  用HashMap存储每个字符串中的单词对应的parrtern中的同位置的字符。
2.  循环遍历时，每次先用parrtern中的同位置的char和当前位置对应的char对比，如果不同就不对返回false
3.  随后还要获取同位置的char的上次出现位置，拿到下标信息后去取对应的单词，并和当前单词对比，如果不同也返回false

## 2.2 代码 ##

class Solution { 
        public boolean wordPattern(String pattern, String str) { 
            String[] strs = str.split(" ");
            char[] pc = pattern.toCharArray();
            if(strs.length != pc.length){ 
                return false;
            }
            Map<String,Character> scMap = new HashMap<>();
            int[] postion = new int[256];
            for(int i = 0; i < pc.length; i++){ 
                char c = pc[i];
                
                String currentStr = strs[i];
                Character ch = scMap.get(currentStr);
                
                if(ch != null ){ 
                    if(c != ch){ 
                        return false;
                    }    
                }else{ 
                    scMap.put(currentStr, c);
                }
                int p = postion[c];
                if(p != 0){ 
                    String oldStr = strs[p - 1];
                    if(!oldStr.equals(currentStr)){ 
                        return false;
                    }
                }
                postion[c] = i + 1;
            }
            return true;
        }
    }

## 2.3 时间复杂度 ##

![在这里插入图片描述][2020051014173073.png]  
O(N)

## 2.4 空间复杂度 ##

O(N)

[2020051014173073.png]: /images/20230312/8a2f82bbcd3e4866955beb34bf5f8941.png