leetcode
leetcode 201 ~ 250
有效的字母异位词

有效的字母异位词

难度:

标签:

题目描述

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

 

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

 

提示:

  • 1 <= s.length, t.length <= 5 * 104
  • s 和 t 仅包含小写字母

 

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

代码结果

运行时间: 19 ms, 内存: 16.1 MB

// Java solution using Java Streams to check if two strings are anagrams
// Approach: Sort both strings and check if they are equal
 
import java.util.Arrays;
 
public class AnagramCheckerStream {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        return Arrays.stream(s.split("")).sorted().collect(Collectors.joining())
                .equals(Arrays.stream(t.split("")).sorted().collect(Collectors.joining()));
    }
 
    public static void main(String[] args) {
        AnagramCheckerStream checker = new AnagramCheckerStream();
        System.out.println(checker.isAnagram("anagram", "nagaram")); // true
        System.out.println(checker.isAnagram("rat", "car")); // false
    }
}

解释

方法:

这个题解的思路是先对两个字符串 s 和 t 分别做去重排序，得到两个字符集合 lst1 和 lst2。如果两个集合长度不同，直接返回 False。然后遍历其中一个集合，比较每个字符在原字符串 s 和 t 中出现的次数，如果次数不同则返回 False，否则遍历结束后返回 True。

时间复杂度:

O(nlogn)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么在检查是否为字母异位词时选择使用排序的方法？这种方法在什么情况下可能不是最优的？
▷
排序的方法是一种直观且容易理解的方法来检查两个字符串是否为字母异位词，因为它将字符串重组为标准形式，使比较变得简单。然而，这种方法的时间复杂度通常是O(n log n)，主要由排序操作决定。在字符串非常长或需要高效处理大量数据的情况下，这可能不是最优的。更高效的方法可能是使用哈希表来统计每个字符出现的次数，这样的时间复杂度可以降低到O(n)。
🦆
在代码中使用了`sorted(set(s))`，去重后再排序，这是否真的必要？去重是否会影响判断字符串是否为字母异位词的准确性？
▷
在这个题解中，使用`sorted(set(s))`去重后再排序是不必要的，且实际上会影响到判断的准确性。因为字母异位词的定义是两个字符串包含相同的字符，每个字符出现的次数也相同，而去重将丢失字符出现的次数信息。正确的做法应该是直接对整个字符串进行排序，然后比较排序后的字符串是否完全相同。
🦆
如果字符串`s`和`t`包含unicode字符，现有的方法是否仍然适用？如果不适用，应该如何修改算法来处理unicode字符？
▷
如果字符串包含Unicode字符，现有的方法理论上仍然适用，因为排序和计数函数通常支持Unicode字符。然而，如果涉及特殊的Unicode字符（如组合字符或变音符号），可能需要额外处理来正确比较。在这种情况下，可以考虑使用Unicode正规化，确保每个字符以相同方式表示，再进行排序或统计字符频率。
🦆
在比较字符计数时，为什么选择遍历排序后的字符集合而不是原字符串？这样做有什么特别的优势吗？
▷
在题解中选择遍历排序后的字符集合主要是为了确保只比较两个字符串共有的字符。这种方法可以减少一些不必要的比较（例如，如果一个字符在一个字符串中不存在，则不需要检查它在另一个字符串中的出现次数）。然而，这种方法在去重后实际上造成了信息丢失，不应在处理字母异位词时使用。更合理的做法是直接对整个字符串进行字符频率统计，然后比较两个字符串中各字符的频率是否完全相同。

相关问题

字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

 

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

 

提示：

  • 1 <= strs.length <= 104
  • 0 <= strs[i].length <= 100
  • strs[i] 仅包含小写字母

回文排列

回文排列

找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

 

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

 示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

 

提示:

  • 1 <= s.length, p.length <= 3 * 104
  • s 和 p 仅包含小写字母
为运算表达式设计优先级最短单词距离