LeetCode 290. 单词规律

Categories:

题目描述
思路分析
1. 解法一：双向映射（推荐）
相似题目

题目描述

✅ 290. 单词规律

思路分析

解法一：双向映射（推荐）

核心思路：

建立字符到单词、单词到字符的双向映射。

遍历模式与单词列表，若映射冲突则失败。

保证一一对应关系即可。

复杂度分析：

时间复杂度：O(n)，其中 n 表示单词数量。

空间复杂度：O(n)，用于哈希映射。

import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean wordPattern(String pattern, String s) {
        String[] words = s.split(" ");
        if (pattern.length() != words.length) {
            return false;
        }

        Map<Character, String> map1 = new HashMap<>();
        Map<String, Character> map2 = new HashMap<>();

        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            String word = words[i];

            if (map1.containsKey(c) && !map1.get(c).equals(word)) {
                return false;
            }
            if (map2.containsKey(word) && map2.get(word) != c) {
                return false;
            }

            map1.put(c, word);
            map2.put(word, c);
        }

        return true;
    }
}

import "strings"

func wordPattern(pattern string, s string) bool {
	words := strings.Split(s, " ")
	if len(pattern) != len(words) {
		return false
	}

	map1 := make(map[byte]string)
	map2 := make(map[string]byte)

	for i := 0; i < len(pattern); i++ {
		c := pattern[i]
		word := words[i]

		if val, ok := map1[c]; ok && val != word {
			return false
		}
		if val, ok := map2[word]; ok && val != c {
			return false
		}

		map1[c] = word
		map2[word] = c
	}

	return true
}

相似题目

题目	难度	考察点
205. 同构字符串	简单	哈希映射
242. 有效的字母异位词	简单	哈希
383. 赎金信	简单	哈希
49. 字母异位词分组	中等	哈希
890. 查找和替换模式	中等	双向映射

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/82761185