本文共 1686 字，大约阅读时间需要 5 分钟。

算法-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”

输入:pattern = “abba”, str = “dog cat cat fish”

输入: pattern = “aaaa”, str = “dog cat cat dog”

输入: pattern = “abba”, str = “dog dog dog dog”

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
   
     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 时间复杂度

2.4 空间复杂度

O(N)

转载地址：http://glpkb.baihongyu.com/