目录
问题描述
过题图片
示例
解决方案
代码实现
题目链接
总结
问题描述
给定两个字符串 s
和 t
,判断它们是否是同构的。如果 s
中的字符可以按某种映射关系替换得到 t
,那么这两个字符串是同构的。具体来说,每个出现的字符都应当映射到另一个字符,同时不改变字符的顺序。不同字符不能映射到同一个字符上,相同字符只能映射到同一个字符上,字符可以映射到自己本身。
过题图片
示例
-
示例 1:
- 输入:
s = "egg"
,t = "add"
- 输出:
true
- 解释:
s
中的'e'
映射到t
中的'a'
,s
中的'g'
映射到t
中的'd'
。
- 输入:
-
示例 2:
- 输入:
s = "foo"
,t = "bar"
- 输出:
false
- 解释:
s
中的两个'o'
不能映射到t
中的两个不同的字符'a'
和'r'
。
- 输入:
-
示例 3:
- 输入:
s = "paper"
,t = "title"
- 输出:
true
- 解释:
s
中的'p'
映射到t
中的't'
,s
中的'a'
映射到t
中的'i'
,依此类推。
- 输入:
解决方案
为了解决这个问题,我们可以使用哈希表(HashMap
)来存储字符之间的映射关系。以下是解决方案的详细步骤:
-
检查长度:首先检查两个字符串的长度是否相等。如果不相等,直接返回
false
。 -
初始化哈希表:创建两个
HashMap
,一个用于存储s
中字符到t
中字符的映射(mapS
),另一个用于存储t
中字符到s
中字符的映射(mapT
)。 -
遍历字符串:遍历字符串
s
和t
中的每个字符。 -
检查映射关系:
- 如果
s
中的字符已经在mapS
中有映射,检查这个映射是否与t
中对应的字符相等。如果不等,返回false
。 - 如果
s
中的字符不在mapS
中,检查t
中的字符是否已经在mapT
中有映射。如果有,返回false
。 - 如果
t
中的字符没有在mapT
中映射,将s
中的字符和t
中的字符分别添加到mapS
和mapT
中。
- 如果
-
返回结果:如果遍历结束后没有返回
false
,则两个字符串是同构的,返回true
。
代码实现
java
import java.util.HashMap;
import java.util.Map;class Solution {public boolean isIsomorphic(String s, String t) {if (s.length() != t.length()) {return false;}Map<Character, Character> mapS = new HashMap<>();Map<Character, Character> mapT = new HashMap<>();for (int i = 0; i < s.length(); i++) {char c1 = s.charAt(i);char c2 = t.charAt(i);if (mapS.containsKey(c1)) {if (mapS.get(c1) != c2) {return false;}} else {if (mapT.containsKey(c2)) {return false;}mapS.put(c1, c2);mapT.put(c2, c1);}}return true;}
}
题目链接
205. 同构字符串 - 力扣(LeetCode)
总结
通过使用哈希表存储字符之间的映射关系,我们可以有效地判断两个字符串是否是同构的。这种方法的时间复杂度为 O(n),其中 n 是字符串的长度,空间复杂度也为 O(n),用于存储映射关系。这种方法简单且高效,适用于解决同构字符串问题。