Valid Anagram

Companies:
  • Amazon Interview Questions
  • Apple Interview Questions
  • Bloomberg Interview Questions
  • Facebook Interview Questions
  • Google Interview Questions
  • Oracle Interview Questions

Valid Anagram

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

Example 1:

Input: s = "computer" t = "omcupert"
Output: true

Example 2:

Input: s = "apple" t = "pllaa"
Output: false

Note:

You may assume the string contains only lowercase alphabets.

Solution:

An anagram is produced by the rearrangement of the letters of the first word into second one. String s is an anagram of t only if rearrangements of the letters of the string s will give string t. This means length of both strings should be equal also.

This can be done using sorting method. We will first check of the both the strings if of equal length, then we will sort both the strings. After sorting we should get identical strings.

Implementation:

Java:

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    char[] str1 = s.toCharArray();
    char[] str2 = t.toCharArray();
    Arrays.sort(str1);
    Arrays.sort(str2);
    return Arrays.equals(str1, str2);
}

Complexity Analysis:

  • Time Complexity: Sorting will cost O(nlogn) time and comarison will cost us O(n) time. Hence overall time is O(nlogn).

  • Space Complexity: O(1), although in java toCharArray() uses O(n) space but we will ignore it in general solution because it is language depended detail and also it depends on how the function is designed.
Scroll to Top