Skip to content

LeetCode: 242-Valid Anagram 解題紀錄

題目

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 * 104
  • s and t consist 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) 可能就是最好的決定。如果你不介意少掉練習機會的話。

References

Read More

Tags:

Leave a Reply