What’s the time complexity of this anagram checker?

Tags: ,



What is the time complexity of this method? I read that time complexity of contains() method of String is O(n) and I’m using it inside my loop that goes over the input string is the time complexity O(n2)?

public static boolean isAnagram(String str, String str1) {
    if(str.length() != str1.length()) {
        return false;
    }
    
    for(int i = 0; i < str.length(); i++) {
        String letter = String.valueOf(str.charAt(i));
        
        if(!str1.contains(letter)) {
            return false;
        }
        
        letter = String.valueOf(str1.charAt(i));
        if(!str.contains(letter)) {
            return false;
        }
    }
                
    return true;
}

Answer

Yup O(n^2) since there is n number of iteration for the for loop and each iteration call contains twice



Source: stackoverflow