当前位置：首页 > backend >正文

力扣经典算法篇-50-单词规律(双哈希结构+正反向求解）

backend 2025/8/13 10:55:36

1、题干

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

2、解题

方法一：（哈希表）

本题要实现pattern的字符和s字符串的映射关系是否都一致。可以使用哈希结构进行求解，当key一致时，校验value是否也一致。如果存在不一致则说明不符合规则。

注意：
如果value一致，key不一致，实际也不满足题意。所以需要定义两个哈希结构进行正向和反向的校验。

代码示例：

import java.util.HashMap;
import java.util.Map;public class Test57 {public static boolean wordPattern(String pattern, String s) {String[] wordArr = s.split(" ");if (wordArr.length != pattern.length()) {return false;}Map<Character, String> map = new HashMap<>();   // 正向 字符到字符串的关系Map<String, Character> map1 = new HashMap<>();  // 反向 字符串到字符的关系for (int i = 0; i < wordArr.length; i++) {char ch = pattern.charAt(i);String value = wordArr[i];if (map.containsKey(ch)) {                    // 正向校验if (!wordArr[i].equals(map.get(ch))) {return false;}} else if (map1.containsKey(value)) {        // 反向校验if (ch != (map1.get(value))) {return false;}} else {map.put(ch, value);map1.put(value, ch);}}return true;}public static void main(String[] args) {String pattern = "abba";String s = "dog cat cat dog";System.out.println(wordPattern(pattern, s));}
}