算法
, ,

判断变形词

Catalogue
  1. 1. 问题
  2. 2. 回答

问题

给定两个字符串 str1 和 str2，如果 str1 和 str2 中出现的字符种类一样且每种字符出现的次数也一样，那么 str1 与 str2 互为变形词。请实现函数判断两个字符串是否互为变形词。

【举例】
str1=＂123＂，str2=＂231＂，返回 true。str1=＂123＂，str2=＂2331＂，返回 false。

回答

  1. @reynd Python3
1
2
3
4
5
6
7
8
9
10
11
12
13
def isAnagram(self, s: str, t: str) -> bool:
    if s =="" and t == "":
        return True

    if len(s) != len(t) or len(set(s)) != len(set(t)):
        return False

    for char in set(s):
        s_count = s.count(char)
        t_count = t.count(char)
        if s_count != t_count:
            return False
        return True

主要利用了 set 的内置优化和特性减少运算，以及使用布尔运算提高效率。

执行用时 : 48 ms, 在所有 Python3 提交中击败了 98.93% 的用户
内存消耗 : 14 MB, 在所有 Python3 提交中击败了 29.70% 的用户

  1. @bob C++

如果字符串 str1 和 str2 长度不同，直接返回 false。

如果长度相同，假设出现字符的编码值在 0~255 之间，那么先申请一个长度为 256 的
整型数组 map，map[a]=b 代表字符编码为 a 的字符出现了 b 次，初始时 map[0-255]的值都是 0。

然后遍历字符串 str1, 统计每种字符出现的数量，比如遍历到字符 ‘a’，其编码值为 97，则令 map[97]++。这样 map 就成了 str1 中每种字符的词频统计表。

然后遍历字符串 str2，每遍历到一个字符，都在 map 中把词频减下来，比如遍历到字符 ‘a’，其编码值为 97，则令 map[97]--，如果减少之后的值小于 0，直接返回 false。

如果遍历完 str2，map 中的值也没出现负值，则返回 true。