Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Valid Anagram

Problem Statement

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, using all the original letters exactly once.

Example 1:

Input: s = "listen", t = "silent"
Output: true

Example 2:

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

Example 3:

Input: s = "hello", t = "world"
Output: false

Constraints:

  • 1 <= s.length, t.length <= 5 * 10<sup>5</sup>
  • s and t consist of lowercase English letters.

.....

.....

.....

Like the course? Get enrolled and start learning!
Utsha Saha

Utsha Saha

· 3 years ago

Return the following:

return sorted(s) == sorted(t)

Show 1 reply
C

chidi.nwaka

· 2 years ago

Since our two input strings s and t are only to be comprised of lowercase english letters, this sets the maximum number of unique letters we could encounter to be 26, regardless of string size. Because of this, our mapping of letters to counts is never going to contain more than 26 active keys at any moment. Thus, our space complexity is bounded to O(26) = O(1).

However, the space demand does not grow reliably as a function of the string input size, meaning it is not O(N) space.

adi berkowitz

adi berkowitz

· 2 years ago

Use a hashmap

from collections import defaultdict
class Solution:
  def isAnagram(self, s, t):
    # TODO: Write your code here
    counter = defaultdict(int)
    for c in s:
      counter[c] += 1
    for c in t:
      if c in counter:
        counter[t] -= 1
      else:
        return False
    
    return sum(counter.values()) == 0
Show 1 reply
Văn Trần Phú Quí

Văn Trần Phú Quí

· 2 years ago

I found this solution is simpler than posted solution. Just 1 question, do we need to check if length of s and t is equal to other?

class Solution {
  isAnagram(s, t) {
    if(s.length !== t.length) return false;
    for(let i = 0; i < s.length; i++){
      if(!t.includes(s[i])){
        return false;
      }
    }
    return true;
  }
};
Show 3 replies
Jayvijay Shah

Jayvijay Shah

· 2 years ago

public boolean isAnagram(String s, String t) {
    int sum1 = 0;
    int sum2 = 0;
    for(int i = 0; i < s.length(); i++) {
      sum1 += (int) s.charAt(i);
    }
    for(int i = 0; i < t.length(); i++) {
      sum2 += (int) t.charAt(i);
    }
    return sum1 == sum2;
  }
Show 1 reply
kalathilhemanth

kalathilhemanth

· a year ago

class Solution:
  def isAnagram(self, s, t):
  
    char_t = list(t)
    char_s = list(s)
    for x in s:
      try:
        char_t.remove(x)
        char_s.remove(x)
      except:
        return False
    
    if len(char_s) == 0 and len(char_t) == 0:
      return True
      
    return False
J

jarrett

· a year ago

Sort the characters in the two strings. If they're equal, they're anagrams.

func (sol *Solution) isAnagram(s, t string) bool {

bs := []byte(s)
bt := []byte(t)
slices.Sort([]byte(bs))
slices.Sort([]byte(bt))

if string(bs) == string(bt) {
   return true
}

return false

}

It's annoying that the version of Go on this site is ancient - 1.13.

J

jan.a.szumski

· 6 months ago

if s and t only contain lowercase english letters, then freqMap.keySet() has the size of up to 26. Therefore Hash map validation (second loop) can be considered to run in constant O(1) time, since it iterates at most 26 times.

wasim ahmed

wasim ahmed

· 5 months ago

class Solution:
  def isAnagram(self, s, t):
    # TODO: Write your code here
    s_list =[0 for i in range(26)]
    t_list = [0 for i in range(26)]
    for ch in s:
      index = ord(ch.upper()) - 65
      s_list[index] += 1
    for ch in t:
      index = ord(ch.upper()) - 65
      t_list[index] += 1
    for i in range(26):
      if s_list[i] != t_list[i]:
        return False
    return True
P

phuc.do.vinh

· 2 months ago

class Solution {
  public boolean isAnagram(String s, String t) {
    int total = 0;
    String combine = s + t;
    for (int i = 0; i < combine.length(); i++) {
      if (i < s.length()) {
        total += combine.charAt(i);
      } else {
        total -= combine.charAt(i);
      }
    }
    return total == 0;
  }
}