242. Valid anagram

242_solution1_sorting.c

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

static int cmp(const void *a, const void *b) {
    return (*(const unsigned char *)a) - (*(const unsigned char *)b);
}

bool isAnagram(char *s, char *t) {
    size_t sLen = strlen(s);
    size_t tLen = strlen(t);
    if (sLen != tLen) {
        return false;
    }

    char *sCopy = strdup(s);
    char *tCopy = strdup(t);
    qsort(sCopy, sLen, sizeof(char), cmp);
    qsort(tCopy, tLen, sizeof(char), cmp);

    bool result = strcmp(sCopy, tCopy) == 0;

    free(sCopy);
    free(tCopy);
    return result;
}

242_solution2_hashmap.c

#include <stdbool.h>
#include <string.h>

bool isAnagram(char *s, char *t) {
    size_t sLen = strlen(s);
    size_t tLen = strlen(t);
    if (sLen != tLen) {
        return false;
    }

    /* byte-value histogram: stands in for a hashmap over the 0-255 key space */
    int counts[256] = {0};
    for (size_t i = 0; i < sLen; i++) {
        counts[(unsigned char)s[i]]++;
    }

    for (size_t i = 0; i < tLen; i++) {
        counts[(unsigned char)t[i]]--;
        if (counts[(unsigned char)t[i]] < 0) {
            return false;
        }
    }

    return true;
}

242_solution3_alphabet_only.c

/* works if chars are a-z only */
#include <stdbool.h>
#include <string.h>

bool isAnagram(char *s, char *t) {
    size_t sLen = strlen(s);
    size_t tLen = strlen(t);
    if (sLen != tLen) {
        return false;
    }

    int count[26] = {0};
    for (size_t i = 0; i < sLen; i++) {
        count[s[i] - 'a']++;
        count[t[i] - 'a']--;
    }

    for (int i = 0; i < 26; i++) {
        if (count[i] != 0) {
            return false;
        }
    }

    return true;
}

242_solution4_unicode.c

/* decodes UTF-8 to code points; C has no native unicode string type */
#include <stdbool.h>
#include <string.h>

typedef struct {
    int codepoint;
    int count;
} CodepointCount;

static int decode_utf8(const unsigned char *s, size_t len, size_t *i) {
    unsigned char c = s[*i];
    int codepoint;
    int extraBytes;

    if ((c & 0x80) == 0) {
        codepoint = c;
        extraBytes = 0;
    } else if ((c & 0xE0) == 0xC0) {
        codepoint = c & 0x1F;
        extraBytes = 1;
    } else if ((c & 0xF0) == 0xE0) {
        codepoint = c & 0x0F;
        extraBytes = 2;
    } else {
        codepoint = c & 0x07;
        extraBytes = 3;
    }

    for (int k = 0; k < extraBytes && *i + 1 < len; k++) {
        (*i)++;
        codepoint = (codepoint << 6) | (s[*i] & 0x3F);
    }

    (*i)++;
    return codepoint;
}

static int find_or_add(CodepointCount *table, int *tableSize, int codepoint) {
    for (int i = 0; i < *tableSize; i++) {
        if (table[i].codepoint == codepoint) {
            return i;
        }
    }
    table[*tableSize].codepoint = codepoint;
    table[*tableSize].count = 0;
    (*tableSize)++;
    return *tableSize - 1;
}

bool isAnagram(char *s, char *t) {
    size_t sLen = strlen(s);
    size_t tLen = strlen(t);

    CodepointCount table[512];
    int tableSize = 0;

    int sCount = 0;
    for (size_t i = 0; i < sLen;) {
        int cp = decode_utf8((unsigned char *)s, sLen, &i);
        table[find_or_add(table, &tableSize, cp)].count++;
        sCount++;
    }

    int tCount = 0;
    for (size_t i = 0; i < tLen;) {
        int cp = decode_utf8((unsigned char *)t, tLen, &i);
        table[find_or_add(table, &tableSize, cp)].count--;
        tCount++;
    }

    if (sCount != tCount) {
        return false;
    }

    for (int i = 0; i < tableSize; i++) {
        if (table[i].count != 0) {
            return false;
        }
    }

    return true;
}

242_solution1_sorting.cpp

#include <algorithm>
#include <string>
using namespace std;

class Solution {
public:
  bool isAnagram(string s, string t) {
    if (s.size() != t.size())
      return false;
    sort(s.begin(), s.end());
    sort(t.begin(), t.end());
    return s == t;
  }
};

242_solution2_hashmap.cpp

#include <string>
#include <unordered_map>
using namespace std;

// the negative check plus the length check together
// guarantee the map is all zeros at the end

class Solution {
public:
  bool isAnagram(string s, string t) {
    if (s.size() != t.size())
      return false;
    unordered_map<char, int> map;

    for (char c : s)
      map[c]++;

    // default-constructs a new entry
    // when the key isn't found
    for (char c : t) {
      if (--map[c] < 0)
        return false;
    }
    return true;
  }
};

242_solution3_alphabet_only.cpp

#include <string>
using namespace std;
// works if chars are a-z only
class Solution {
public:
  bool isAnagram(string s, string t) {
    if (s.size() != t.size())
      return false;

    int count[26] = {0};
    for (int i = 0; i < s.size(); i++) {
      count[s[i] - 'a']++;
      count[t[i] - 'a']--;
    }

    for (int c : count) {
      if (c != 0)
        return false;
    }

    return true;
  }
};

242_solution4_unicode.cpp

#include <codecvt>
#include <locale>
#include <string>
#include <unordered_map>
using namespace std;

class Solution {
public:
  bool isAnagram(string s, string t) {
    std::wstring_convert<std::codecvt_utf8<char32_t>, char32_t> converter;
    std::u32string s32 = converter.from_bytes(s);
    std::u32string t32 = converter.from_bytes(t);

    if (s32.size() != t32.size())
      return false;

    unordered_map<char32_t, int> map;
    for (char32_t c : s32)
      map[c]++;
    for (char32_t c : t32) {
      if (--map[c] < 0)
        return false;
    }
    return true;
  }
};

242_solution1_sorting.go

package solution

import "sort"

func isAnagram(s string, t string) bool {
    if len(s) != len(t) {
        return false
    }

    sRunes := []rune(s)
    tRunes := []rune(t)
    sort.Slice(sRunes, func(i, j int) bool { return sRunes[i] < sRunes[j] })
    sort.Slice(tRunes, func(i, j int) bool { return tRunes[i] < tRunes[j] })

    return string(sRunes) == string(tRunes)
}

242_solution2_hashmap.go

package solution

func isAnagram(s string, t string) bool {
    if len(s) != len(t) {
        return false
    }

    // range over a string yields runes, so this is unicode-safe by default.
    counts := make(map[rune]int)
    for _, c := range s {
        counts[c]++
    }

    for _, c := range t {
        counts[c]--
        if counts[c] < 0 {
            return false
        }
    }

    return true
}

242_solution3_alphabet_only.go

// works if chars are a-z only
package solution

func isAnagram(s string, t string) bool {
    if len(s) != len(t) {
        return false
    }

    var count [26]int
    for i := 0; i < len(s); i++ {
        count[s[i]-'a']++
        count[t[i]-'a']--
    }

    for _, c := range count {
        if c != 0 {
            return false
        }
    }

    return true
}

242_solution4_unicode.go

package solution

import "unicode/utf8"

func isAnagram(s string, t string) bool {
    // Explicit rune-count based length check; the map below (like solution2)
    // already iterates by rune, so Go needs no extra step for full unicode
    // safety beyond what range already gives.
    if utf8.RuneCountInString(s) != utf8.RuneCountInString(t) {
        return false
    }

    counts := make(map[rune]int)
    for _, c := range s {
        counts[c]++
    }

    for _, c := range t {
        counts[c]--
        if counts[c] < 0 {
            return false
        }
    }

    return true
}

242_solution1_sorting.java

import java.util.Arrays;

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }

        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();
        Arrays.sort(sChars);
        Arrays.sort(tChars);

        return Arrays.equals(sChars, tChars);
    }
}

242_solution2_hashmap.java

import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }

        Map<Character, Integer> counts = new HashMap<>();
        for (char c : s.toCharArray()) {
            counts.merge(c, 1, Integer::sum);
        }

        for (char c : t.toCharArray()) {
            Integer remaining = counts.get(c);
            if (remaining == null || remaining == 0) {
                return false;
            }
            counts.put(c, remaining - 1);
        }

        return true;
    }
}

242_solution3_alphabet_only.java

// works if chars are a-z only
class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }

        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
            count[t.charAt(i) - 'a']--;
        }

        for (int c : count) {
            if (c != 0) {
                return false;
            }
        }

        return true;
    }
}

242_solution4_unicode.java

import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean isAnagram(String s, String t) {
        // charAt/toCharArray walk UTF-16 code units and can split surrogate
        // pairs for astral characters; codePoints() iterates full code points.
        int[] sPoints = s.codePoints().toArray();
        int[] tPoints = t.codePoints().toArray();

        if (sPoints.length != tPoints.length) {
            return false;
        }

        Map<Integer, Integer> counts = new HashMap<>();
        for (int cp : sPoints) {
            counts.merge(cp, 1, Integer::sum);
        }

        for (int cp : tPoints) {
            Integer remaining = counts.get(cp);
            if (remaining == null || remaining == 0) {
                return false;
            }
            counts.put(cp, remaining - 1);
        }

        return true;
    }
}

242_solution1_sorting.js

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function (s, t) {
  if (s.length !== t.length) return false;

  const sortStr = (str) => [...str].sort().join("");
  return sortStr(s) === sortStr(t);
};

242_solution2_hashmap.js

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function (s, t) {
  if (s.length !== t.length) return false;

  const counts = new Map();
  for (const c of s) {
    counts.set(c, (counts.get(c) || 0) + 1);
  }

  for (const c of t) {
    const remaining = counts.get(c);
    if (!remaining) return false;
    counts.set(c, remaining - 1);
  }

  return true;
};

242_solution3_alphabet_only.js

// works if chars are a-z only
/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function (s, t) {
  if (s.length !== t.length) return false;

  const count = new Array(26).fill(0);
  const aCode = "a".charCodeAt(0);

  for (let i = 0; i < s.length; i++) {
    count[s.charCodeAt(i) - aCode]++;
    count[t.charCodeAt(i) - aCode]--;
  }

  return count.every((c) => c === 0);
};

242_solution4_unicode.js

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function (s, t) {
  // for...of iterates by Unicode code point (handles surrogate pairs
  // correctly), unlike indexing/charCodeAt which walk UTF-16 code units.
  const codePoints = (str) => [...str];

  const a = codePoints(s);
  const b = codePoints(t);
  if (a.length !== b.length) return false;

  const counts = new Map();
  for (const c of a) counts.set(c, (counts.get(c) || 0) + 1);
  for (const c of b) {
    const remaining = counts.get(c);
    if (!remaining) return false;
    counts.set(c, remaining - 1);
  }

  return true;
};

242_solution1_sorting.py

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

242_solution2_hashmap.py

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

        counts = {}
        for c in s:
            counts[c] = counts.get(c, 0) + 1

        for c in t:
            if c not in counts:
                return False
            counts[c] -= 1
            if counts[c] < 0:
                return False

        return True

242_solution3_alphabet_only.py

# works if chars are a-z only
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        count = [0] * 26
        for cs, ct in zip(s, t):
            count[ord(cs) - ord("a")] += 1
            count[ord(ct) - ord("a")] -= 1

        return all(c == 0 for c in count)

242_solution4_unicode.py

from collections import Counter


class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # Python iterates str by Unicode code point already, so this is
        # unicode-safe by default (unlike C++'s byte-oriented std::string).
        return Counter(s) == Counter(t)

242_solution1_sorting.rs

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

        let mut s_chars: Vec<char> = s.chars().collect();
        let mut t_chars: Vec<char> = t.chars().collect();
        s_chars.sort_unstable();
        t_chars.sort_unstable();

        s_chars == t_chars
    }
}

struct Solution;

242_solution2_hashmap.rs

use std::collections::HashMap;

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

        let mut counts: HashMap<char, i32> = HashMap::new();
        for c in s.chars() {
            *counts.entry(c).or_insert(0) += 1;
        }

        for c in t.chars() {
            match counts.get_mut(&c) {
                Some(count) if *count > 0 => *count -= 1,
                _ => return false,
            }
        }

        true
    }
}

struct Solution;

242_solution3_alphabet_only.rs

// works if chars are a-z only
impl Solution {
    pub fn is_anagram(s: String, t: String) -> bool {
        if s.len() != t.len() {
            return false;
        }

        let mut count = [0i32; 26];
        for (cs, ct) in s.bytes().zip(t.bytes()) {
            count[(cs - b'a') as usize] += 1;
            count[(ct - b'a') as usize] -= 1;
        }

        count.iter().all(|&c| c == 0)
    }
}

struct Solution;

242_solution4_unicode.rs

use std::collections::HashMap;

impl Solution {
    pub fn is_anagram(s: String, t: String) -> bool {
        // chars() already iterates Unicode scalar values, so this is
        // equivalent to solution2 — Rust needs no extra step here, unlike
        // C++'s byte-oriented std::string.
        if s.chars().count() != t.chars().count() {
            return false;
        }

        let mut counts: HashMap<char, i32> = HashMap::new();
        for c in s.chars() {
            *counts.entry(c).or_insert(0) += 1;
        }

        for c in t.chars() {
            match counts.get_mut(&c) {
                Some(count) if *count > 0 => *count -= 1,
                _ => return false,
            }
        }

        true
    }
}

struct Solution;