LeetCode #242 Valid Anagram Solution & Explanation

Klook.com
Post Views: 516

LeetCode Problem

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.

LeetCode#242 Examples and Constraints

Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

Solution

C# Solution

Solution1 – compare with string after order by

public class Solution {
    public bool IsAnagram(string s, string t) {
        s = String.Concat(s.OrderBy(c => c));
        t = String.Concat(t.OrderBy(c => c));

        return s==t;
    }
}

Let’s sort the string with Linq order by first, than compare the difference of them.

If two strings are same, than return true.

❌Solution2 – Dictionary – not recommend, performance is not good

public class Solution {
    public bool IsAnagram(string s, string t) {
        
        Dictionary<char, int> dict1 = toDict(s);
        Dictionary<char, int> dict2 = toDict(t);

        //return dict1.OrderBy(r=>r.Key).SequenceEqual(dict2.OrderBy(r=>r.Key));
        return dict1.Count == dict2.Count && !dict1.Except(dict2).Any();
    }

    public Dictionary<char, int> toDict(string s)
    {
        Dictionary<char, int> dict = new Dictionary<char, int>();
        
        foreach(char i in s)
        {
            if (!dict.ContainsKey(i))
            {
                dict.Add(i, 1);
            }
            else
            {
                dict[i] = dict[i]+1;
            }
        }

        return dict;
    }
}

In the second solution, we make two dictionary which record character as key and appear times as value.

And there have two normal ways to check different or not.

Java Solution

Solution1 – compare with arrays

class Solution {
    public boolean isAnagram(String s, String t) {
        char charArr[] = s.toCharArray();
        char charArr2[] = t.toCharArray();
        
        Arrays.sort(charArr);
        Arrays.sort(charArr2);

        return Arrays.equals(charArr,charArr2);
    }
}

Runtime : 3ms、3ms、3ms ≈ faster than 91%

❌Solution2 – compare with map – not recommend, too slow

class Solution {
    public boolean isAnagram(String s, String t) {
        Map<Character, Integer> map1 = toMap(s);
        Map<Character, Integer> map2 = toMap(t);

        return map1.equals(map2);
    }

    public Map<Character, Integer> toMap(String str)
    {
        Map<Character, Integer> map = new HashMap<Character, Integer>();  

        for (int i = 0; i < str.length(); i++) 
        {
            char c = str.charAt(i);
            if(map.containsKey(c))     
            {
                map.put(c, map.get(c)+1);   
            }
            else
            {
                map.put(c, 1);    
            }
        }

        return map;
    }
}

Runtime : 13ms、13ms、13ms ≈ faster than 46%

Python3 Solution

Solution1 – built-in function sorted

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        list1 = sorted(s)
        list2 = sorted(t)

        return list1 == list2

Runtime : 50ms、53ms、52ms ≈ faster than 80%

JavaScript Solution

Solution1 – built-in sort function and compare array

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
    list1 = s.split("").sort();
    list2 = t.split("").sort();

    console.log(list1);
    console.log(list2);
    return JSON.stringify(list1) === JSON.stringify(list2);
};

Conclusion

🧡If my solution helps, that is my honor!

🧡You can support me by clicking some ad, Thanks a lot

✅If you got any problem about the explanation, please feel free to let me know

The problem link : Valid Anagram – LeetCode

Random post

Tags

Related Posts

Leave a Reply

Your email address will not be published. Required fields are marked *