LeetCode题练习与总结：同构字符串--205

本文主要是介绍LeetCode题练习与总结：同构字符串--205，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目描述

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1:

输入：s = "egg", t = "add"
输出：true

示例 2：

输入：s = "foo", t = "bar"
输出：false

示例 3：

输入：s = "paper", t = "title"
输出：true

提示：

• 1 <= s.length <= 5 * 10^4
• t.length == s.length
• s 和 t 由任意有效的 ASCII 字符组成

二、解题思路

1. 首先检查两个字符串的长度是否相等，如果不相等，直接返回false。
2. 创建两个HashMap，分别用于存储s到t的映射关系和t到s的映射关系。
3. 遍历字符串s和t的每个字符，对于s中的每个字符，检查其在HashMap中的映射是否为t中对应的字符，如果不是，则返回false。
4. 同样，对于t中的每个字符，检查其在另一个HashMap中的映射是否为s中对应的字符，如果不是，则返回false。
5. 如果上述步骤都通过，则说明两个字符串是同构的，返回true。

三、具体代码

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> mapSToT = new HashMap<>();Map<Character, Character> mapTToS = new HashMap<>();for (int i = 0; i < s.length(); i++) {char sChar = s.charAt(i);char tChar = t.charAt(i);// 检查s到t的映射if (mapSToT.containsKey(sChar)) {if (mapSToT.get(sChar) != tChar) {return false;}} else {mapSToT.put(sChar, tChar);}// 检查t到s的映射if (mapTToS.containsKey(tChar)) {if (mapTToS.get(tChar) != sChar) {return false;}} else {mapTToS.put(tChar, sChar);}}return true;}
}

四、时间复杂度和空间复杂度

1. 时间复杂度

• 首先检查两个字符串的长度是否相等，这是一个O(1)的操作，因为字符串的长度属性是预先计算好的。
• 接下来是一个for循环，它遍历字符串s和t的每个字符，循环的次数为字符串的长度n。
• 在循环内部，我们执行了常数时间的操作，包括：
  • 检查字符是否在HashMap中（O(1)）。
  • 获取HashMap中的值（O(1)）。
  • 将键值对插入到HashMap中（O(1)）。

由于HashMap的插入和查找操作的平均时间复杂度是O(1)，因此整个for循环的时间复杂度是O(n)，其中n是字符串的长度。

综上所述，整个函数的时间复杂度是O(n)。

2. 空间复杂度

• 我们使用了两个HashMap，mapSToT和mapTToS，来存储字符之间的映射关系。
• 在最坏的情况下，如果字符串s和t中所有的字符都是唯一的，那么每个HashMap中将会存储n个键值对，其中n是字符串的长度。
• 因此，两个HashMap总共需要O(n)的空间。

综上所述，整个函数的空间复杂度是O(n)。

五、总结知识点

• 类定义 (class 关键字):

  • 定义了一个名为 Solution 的类。

• 方法定义 (public boolean isIsomorphic(String s, String t)):

  • 定义了一个公共方法 isIsomorphic，它接受两个字符串参数 s 和 t，并返回一个布尔值。

• 条件语句 (if):

  • 使用 if 语句来检查两个字符串的长度是否相等。

• 数据结构 - HashMap (import java.util.HashMap;):

  • 导入了 HashMap 类，用于创建散列表来存储键值对。
  • 使用 HashMap 来存储字符之间的映射关系。

• 循环结构 (for 循环):

  • 使用 for 循环来遍历字符串中的每个字符。

• 字符操作 (char sChar = s.charAt(i);):

  • 使用 charAt 方法来获取字符串中指定位置的字符。

• HashMap 操作:

  • 使用 containsKey 方法检查 HashMap 中是否包含特定的键。
  • 使用 get 方法从 HashMap 中获取与键相关联的值。
  • 使用 put 方法将键值对插入到 HashMap 中。

• 逻辑运算 (return false;, return true;):

  • 根据条件判断的结果返回布尔值 true 或 false。

• 字符串长度属性 (s.length()):

  • 使用字符串的 length 属性来获取字符串的长度。

• 变量声明和初始化 (Map<Character, Character> mapSToT = new HashMap<>();):

  • 声明并初始化两个 HashMap 变量，用于存储字符映射关系。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。

这篇关于LeetCode题练习与总结：同构字符串--205的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---