242. Valid Anagram

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

• CTCI 1.2 Check Permutation

Python

Sort the string counts

Consider s has length M; t has length N

• Time: O(NlogN * MlogM)
• Space: O(N+M)

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        s_chars = list(s)
        t_chars = list(t)
        s_chars.sort()
        t_chars.sort()

        for i in range(len(s_chars)-1, -1, -1):
            s_char = s_chars[i]
            if s_char != t_chars[-1]:
                return False
            t_chars.pop()
        return True

Counter

• Time: O(M)
• Space: O(M+N) worst case

from collections import Counter

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        s_counts = Counter(s)
        t_counts = Counter(t)

        for char, count in s_counts.items():
            if char not in t_counts or t_counts[char] != count:
                return False
        return True

Bit Manipulation

• 用一個整數bit_vector作為mapper，每個bit都表示：特定字元的出現次數是否為奇數
  • 第0bit，表示'a'在字串中是否出現次數為奇數
  • 累進時要注意bit有沒有重疊，有重疊往上疊會導致退位
• 最終檢查bit_vector是否只有一個bit為1 - 即該字串的字元組合可以組出迴文
  • b11110 & b00001 = 0，即 (b11110 - 1) & b11110

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        # 1st bit present 'a' is even, 2nd bit present 'b' is event and so on
        bit_vector = 0

        for letter in s:
            mask = 1 << (ord(letter) - ord('a'))
            if bit_vector & mask == 0:
                # bit has overlay
                bit_vector |= mask
            else:
                bit_vector &= ~mask

        return (bit_vector & (bit_vector - 1)) == 0

Rust

Mapper

• Time: O(N)
• Space: O(1)

impl Solution {
    pub fn is_anagram(s: String, t: String) -> bool {
        if s.len() != t.len() {
            return false
        }

        let mut mapper_s = [0; 26];
        let mut mapper_t = [0; 26];

        for i in s.as_bytes().iter() {
            mapper_s[(i-b'a') as usize] += 1;
        }
        for j in t.as_bytes().iter() {
            mapper_t[(j-b'a') as usize] += 1;
        }

        mapper_s == mapper_t
    }
}

Sort the string

• Time: O(NlogN) // by sort
• Space: O(1)

use std::iter::Iterator;
use std::iter::FromIterator;


impl Solution {
    pub fn is_anagram(s: String, t: String) -> bool {
        if s.len() != t.len() {
            return false
        }

        let slice_s: &str = &s[..];
        let slice_t: &str = &t[..];

        let mut chars_s: Vec<char> = slice_s.chars().collect();
        let mut chars_t: Vec<char> = slice_t.chars().collect();

        chars_s.sort_by(|pre, cur| cur.cmp(pre));
        chars_t.sort_by(|pre, cur| cur.cmp(pre));

        let sorted_s = String::from_iter(chars_s);
        let sorted_t = String::from_iter(chars_t);

        sorted_s == sorted_t
    }
}

Plus the Minus

• 一加一減，如果是相同組合，最終mapper應該會都是0

impl Solution {
    pub fn is_anagram(s: String, t: String) -> bool {
        if s.len() != t.len() {
            return false
        }

        let mut mapper = [0; 26];
        for i in s.as_bytes().iter() {
            mapper[(i-b'a') as usize] += 1;
        }

        for i in t.as_bytes().iter() {
            let letter_id = (i - b'a') as usize;
            mapper[letter_id] -= 1;
            if mapper[letter_id] < 0 {
                return false;
            }
        }

        true
    }
}

Bit Manipulation

impl Solution {
    pub fn can_permute_palindrome(s: String) -> bool {
        let mut bit_vector = 0;

        for letter in s.chars() {
            let mask = 1 << (letter as u32 - 'a' as u32);
            if bit_vector & mask == 0 {
                bit_vector |= mask;
            } else {
                bit_vector &= !mask;
            }
        }

        (bit_vector & (bit_vector - 1)) == 0
    }
}