LeetCode 242. Valid Anagram(合法的重排字符串)
题目描述
Given two strings s and t, write a function to determine if t is an anagram of s.
For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.
Note:
You may assume the string contains only lowercase alphabets.
Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?
解法一
思路
想要判断两个字符串是不是“重排”的,只用看字符串中字符出现的次数是不是一一对应就好了。我们可以维持一个counts
数组,对于第一个字符串中的字符,每遇到一个就在counts
中对应位置加1
;而对于第二个字符串中的字符,每遇到一个就在counts
中对应位置减一;最后再检查counts
是不是全部元素都是0
,如果有非0
的元素,那么就说明两个字符串不是“重排”的(字符出现的次数没有一一对应)。
这样做能不能处理“字符串中出现了新的字符”这样的情况呢?当然是可以的,而且处理方法与普通的字符没有任何区别,因为这些“新的字符”最终在counts
中也只会反映为非0
的数,即不是一一对应的。
使用counts
数组的缺点是相当于提前为每个可能的字符分配了初始计数值0
,但对本题来说问题不大,因为字符只可能是小写字母,即counts
数组的大小只需要为26。
这里还可以在算法前加一个前置检查:如果两个字符串长度不相等,那么它们肯定就不是重排的了,也没有必要大费周章去遍历计数了。
Python
class Solution:
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
if len(s) != len(t):
return False
counts = [0] * 26
for item in s:
counts[ord(item) - ord('a')] += 1
for item in t:
counts[ord(item) - ord('a')] -= 1
return all(count == 0 for count in counts)
Java
public class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int[] counts = new int[26];
for (char item : s.toCharArray()) {
counts[item - 'a']++;
}
for (char item : t.toCharArray()) {
counts[item - 'a']--;
}
for (int count : counts) {
if (count != 0) {
return false;
}
}
return true;
}
}
C++
class Solution {
public:
bool isAnagram(string s, string t) {
if (s.length() != t.length()) {
return false;
}
vector<int> counts(26, 0);
for (auto item : s) {
counts[item - 'a']++;
}
for (char item : t) {
counts[item - 'a']--;
}
for (auto count : counts) {
if (count != 0) {
return false;
}
}
return true;
}
};
LeetCode 242. Valid Anagram(合法的重排字符串) - Penguin
[url=http://www.gc28i8wcz8f0x023i4gas10n8oy72a63s.org/]ujqkdwjpxmp[/url]
ajqkdwjpxmp
jqkdwjpxmp http://www.gc28i8wcz8f0x023i4gas10n8oy72a63s.org/
LeetCode 242. Valid Anagram(合法的重排字符串) - Penguin
gerhkvfgw http://www.gfq89cq677fx1zh80695n5aoy04m77pxs.org/
[url=http://www.gfq89cq677fx1zh80695n5aoy04m77pxs.org/]ugerhkvfgw[/url]
agerhkvfgw