LeetCode 刷題紀錄｜242. Valid Anagram (Easy)

Roy Wang

Published in

RoyWannago

8 min readNov 14, 2020

242. Valid Anagram

Link: https://leetcode.com/problems/valid-anagram/solution/

Question

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false

Note:
You may assume the string contains only lowercase alphabets.

先查一下Anagram的定義是什麼：

‘a word or phrase made by using the letters of another word or phrase in a different order: “Neat” is an anagram of “a net”.’

就example來看的話，符合anagram兩組字，代表組成這兩個單字的字母元素與個數會是一樣的：

anagram 是 3 個 a, 1 個 n, 1 個 g, 1 個r, 1 個 m
nagaram 也是 a * 3, n * 1, g * 1, r * 1, m * 1

這兩個字就是 anagram, 預期的產出是 true

a , b -> 不是
aaavv, avvaa -> 是
rot, rat -> 不是
ret, etr -> 是

Answers

Sorting
Hash Table

這題有兩種可能的作法，一種是用排序把字串按a-z順序排好之後，比對兩個字串是否相等；另一種做法是用Hash Table去存每個字母的個數，以此比對個數是否相同。

Solution 1: Sorting

Sorting 的作法很簡單，就是把兩個字串都排整齊了，就可以把兩個字串比對

Example: “
把 ‘anna’, ‘nana’ 排序成 => aann, aann

Sorting 需要將 String 先 split 成 Array

string = 'hello'
array = string.split('')
console.log(array)
// ['h','e','l','l','o']

因為我用的是 Javascript，沒辦法用 array1 === array2 的方式來判別兩 array 是否相等（因為兩個 array variables 是指向不同 references）

但是，可以判別兩字串是否相等，所以先將字串轉成array去排序，排序完再轉回字串比較是否相等

Example:

[1,2,3] === [1,2,3]         // return false
[1,2,3].toString() == [1,2,3].toString()      // true
[1,2,3].join(',') == [1,2,3].join(',')        // true

Code:

var isAnagram = function(s, t) {
    if (s.length !== t.length) return false;
    
    s = s.split('').sort().join('');
    t = t.split('').sort().join('');
    
    return s == t // 也可以寫成 one-liner
};// 用 [...]var isAnagram = function(s, t) {
    if (s.length !== t.length) return false;
    
    const arrays = [...s].sort();
    const arrayt = [...t].sort();
    
    for (let i = 0; i < s.length; i++) {
        if (arrays[i] !== arrayt[i]) {
            return false
        }
    }
    
    return true
};

Complexity:

Time: O(nlogn)
Space: O(1)

Solution 2: Hash Table

Complexity:

Time: O(n)
Space: O(1)

Hash Table 這裡有幾種作法，主要是幾種 loop 的作法不太一樣

第一個 loop一個加一個減個數，第二個 loop 檢查是否每個字母總和都是零
第一個 loop 專門增加，第二個 loop 專門減少，減少的過程若小於零 return false

Hash Table 1

數兩個字串的各字母個數是否相等，用 counter 或 hash table 來存 {字母: 數量}

比較省時的方式：不需要存兩個 hash map, 在一個loop之中，一個加一個減，若相等，總和最後應該都要是零

最後再用一個loop檢查0

var isAnagram3 = function (s, t) {
  if (s.length !== t.length) return false;  const sMap = {};  for (let i = 0; i < s.length; i++) {
    sMap[s[i]] == undefined ? (sMap[s[i]] = 1) : sMap[s[i]]++;
    sMap[t[i]] == undefined ? (sMap[t[i]] = -1) : sMap[t[i]]--;
  }  for (key in sMap) {
    if (sMap[key] !== 0) return false;
  }  return true;
};

看到用map來實作覺得很有趣, 試玩看看 map

// map
var isAnagram4 = function (s, t) {
  if (s.length !== t.length) return false;  const map = {};
  s.split('').map((char) => (map[char] = map[char] ? map[char] + 1 : 1));
  t.split('').map((char) => (map[char] = map[char] ? map[char] - 1 : -1));  return Object.keys(map).every((k) => map[k] === 0);
};

Hash Table 2

也可以分開兩個loop, 一個專門增加，一個專門減少，減少的過程若小於零 return false

var isAnagram5 = function (s, t) {
  if (s.length !== t.length) return false;  const sMap = {};  for (let i = 0; i < s.length; i++) {
    sMap[s[i]] === undefined ? (sMap[s[i]] = 1) : sMap[s[i]]++;
  }  for (let i = 0; i < s.length; i++) {
    sMap[t[i]] === undefined ? (sMap[t[i]] = -1) : sMap[t[i]]--;
    if (sMap[t[i]] < 0) return false;
  }  return true;
};

Python 作法:

class Solution:
    def isAnagram1(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
    
        dict = {}
        for c in s:
            if c not in dict:
                dict[c] = 1
            else:
                dict[c] += 1
        for c in t:
            if c not in dict:
                return False
            else:
                dict[c] -= 1
                if dict[c] < 0:
                    return False
        return True# Python 的 One-linerclass Solution:
    def isAnagram2(self, s: str, t: str) -> bool:
        return sorted(s) == sorted(t)# 在討論區看到的有趣作法，速度超快 faster than 97.43% of Python3 submissionsclass Solution:
    def isAnagram3(self, s: str, t: str) -> bool:
        return all(s.count(x) == t.count(x) for x in 'abcdefghijklmnopqrstuvwxzy')

這題不算難，但好玩的是可以用很多不同的角度去切入，多看看不同的作法

Javascript 還好有多新的函數都還沒試過，希望之後可以多試試~

新手上路，如果有寫錯的地方歡迎大力糾正，歡迎留言討論或是到我的Socials找我~謝謝觀看！

About Roy

Social Media
Facebook — RoyWannago
Twitter — @roywannago
Instagram — @royflwdesign
Website — roywannago.com

LeetCode 刷題紀錄 ｜242. Valid Anagram (Easy)