Last Updated on 2023-12-16 by Clay
題目
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:Input: s = “anagram”, t = “nagaram” Output: true
Example 2:Input: s = “rat”, t = “car” Output: false
Constraints:
1 <= s.length, t.length <= 5 * 104sandtconsist of lowercase English letters.
Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?
解題思路
這題是很單純的比較 s 和 t 是否為變位詞，簡單來說就是他們需要字元在排序過後要完全一模一樣。
如果需要使用額外空間極度少，那自然就是將兩字串組重新排序後直接比較是否相等；這樣的時間複雜度是 O(n*log(n))，空間複雜度是 O(1)。
如果是講求計算速度，那自然是使用陣列或字典。使用陣列計算速度會比較快，但就無法彈性地處理非 unicode 的情況（Follow up 的要求），所以可能用字典比較靈活。這樣的時間複雜度跟空間複雜度都是 O(n)。
下方我使用字典來解，因為這順便符合 Follow up 的提問。
C++ 範例程式碼
class Solution {
public:
bool isAnagram(string s, string t) {
// Base case
if (s.size() != t.size()) {
return false;
}
// Init
unordered_map<char, int> sMap;
unordered_map<char, int> tMap;
// Count
for (int i=0; i<s.size(); ++i) {
++sMap[s[i]];
++tMap[t[i]];
}
return sMap == tMap;
}
};Python
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
# Base case
if len(s) != len(t):
return False
# Init
sMap = {};
tMap = {};
# Count
for i in range(len(s)):
sMap[s[i]] = sMap.get(s[i], 0) + 1
tMap[t[i]] = tMap.get(t[i], 0) + 1
return sMap == tMap
但在 Python 的情況下，使用內建的 Counter 可能性能更好。直接 return Counter(s) == Counter(t) 可能就是最好的決定。如果你不介意少掉練習機會的話。