LeetCode 205. 同构字符串

Categories:

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

题目描述

✅ 205. 同构字符串

思路分析

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

核心思路：

同构要求字符一一映射，且映射是双向唯一。

用两个数组分别记录 s -> t 和 t -> s 的映射。

若已建立映射但与当前字符不一致，则不是同构。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(1)，字符集固定大小。

import java.util.Arrays;

class Solution {
    public boolean isIsomorphic(String s, String t) {
        int[] mapST = new int[256];
        int[] mapTS = new int[256];
        Arrays.fill(mapST, -1);
        Arrays.fill(mapTS, -1);

        for (int i = 0; i < s.length(); i++) {
            int a = s.charAt(i);
            int b = t.charAt(i);

            if (mapST[a] == -1 && mapTS[b] == -1) {
                mapST[a] = b;
                mapTS[b] = a;
                continue;
            }

            if (mapST[a] != b || mapTS[b] != a) {
                return false;
            }
        }
        return true;
    }
}

func isIsomorphic(s string, t string) bool {
	mapST := make([]int, 256)
	mapTS := make([]int, 256)
	for i := 0; i < 256; i++ {
		mapST[i] = -1
		mapTS[i] = -1
	}

	for i := 0; i < len(s); i++ {
		a := s[i]
		b := t[i]

		if mapST[a] == -1 && mapTS[b] == -1 {
			mapST[a] = int(b)
			mapTS[b] = int(a)
			continue
		}

		if mapST[a] != int(b) || mapTS[b] != int(a) {
			return false
		}
	}
	return true
}

相似题目

题目	难度	考察点
290. 单词规律	简单	哈希映射
205. 同构字符串	简单	哈希映射
242. 有效的字母异位词	简单	计数/哈希
383. 赎金信	简单	计数/哈希
49. 字母异位词分组	中等	哈希映射
387. 字符串中的第一个唯一字符	简单	计数/哈希

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/39186524