Проверка на анаграмму

Проверка на анаграмму в Java

Объяснение задачи

Анаграмма — это слово или фраза, составленные из тех же букв, что и исходное слово, но в другом порядке. Например, "listen" и "silent" содержат одинаковый набор букв: l, i, s, t, e, n.

Решение 1: С использованием массива (O(n))

Это оптимальное решение по времени. Подсчитываем частоту каждого символа:

public class AnagramChecker {
    public static boolean isAnagram(String str1, String str2) {
        if (str1.length() != str2.length()) {
            return false;
        }
        
        int[] charCount = new int[26];
        
        for (int i = 0; i < str1.length(); i++) {
            charCount[str1.charAt(i) - 'a']++;
            charCount[str2.charAt(i) - 'a']--;
        }
        
        for (int count : charCount) {
            if (count != 0) {
                return false;
            }
        }
        
        return true;
    }
}

Решение 2: С HashMap (более универсальное)

Для поддержки Unicode символов используем HashMap:

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

public class AnagramChecker {
    public static boolean isAnagramHashMap(String str1, String str2) {
        if (str1.length() != str2.length()) {
            return false;
        }
        
        Map<Character, Integer> charMap = new HashMap<>();
        
        for (char c : str1.toCharArray()) {
            charMap.put(c, charMap.getOrDefault(c, 0) + 1);
        }
        
        for (char c : str2.toCharArray()) {
            if (!charMap.containsKey(c)) {
                return false;
            }
            charMap.put(c, charMap.get(c) - 1);
            if (charMap.get(c) < 0) {
                return false;
            }
        }
        
        return true;
    }
}

Решение 3: С игнорированием пробелов и регистра

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

public class AnagramChecker {
    public static boolean isAnagramIgnoreSpaceCase(String str1, String str2) {
        String cleaned1 = str1.replaceAll("\\s+", "").toLowerCase();
        String cleaned2 = str2.replaceAll("\\s+", "").toLowerCase();
        
        if (cleaned1.length() != cleaned2.length()) {
            return false;
        }
        
        Map<Character, Integer> charMap = new HashMap<>();
        
        for (char c : cleaned1.toCharArray()) {
            if (Character.isLetterOrDigit(c)) {
                charMap.put(c, charMap.getOrDefault(c, 0) + 1);
            }
        }
        
        for (char c : cleaned2.toCharArray()) {
            if (Character.isLetterOrDigit(c)) {
                if (!charMap.containsKey(c)) {
                    return false;
                }
                charMap.put(c, charMap.get(c) - 1);
            }
        }
        
        return charMap.values().stream().allMatch(count -> count == 0);
    }
}

Решение 4: Сортировка (O(n log n))

import java.util.Arrays;

public class AnagramChecker {
    public static boolean isAnagramSorted(String str1, String str2) {
        if (str1.length() != str2.length()) {
            return false;
        }
        
        char[] arr1 = str1.toCharArray();
        char[] arr2 = str2.toCharArray();
        
        Arrays.sort(arr1);
        Arrays.sort(arr2);
        
        return Arrays.equals(arr1, arr2);
    }
}

Полный пример с тестами

public class AnagramTest {
    public static void main(String[] args) {
        System.out.println(AnagramChecker.isAnagram("listen", "silent")); // true
        System.out.println(AnagramChecker.isAnagram("triangle", "integral")); // true
        System.out.println(AnagramChecker.isAnagram("hello", "world")); // false
        System.out.println(AnagramChecker.isAnagramIgnoreSpaceCase("Dormitory", "Dirty room")); // true
    }
}

Сравнение подходов

Вывод

HashMap решение оптимально для интервью, так как демонстрирует:

• Понимание работы структур данных
• Анализ временной и пространственной сложности
• Универсальность для любых символов (не только ASCII)
• Чистый и читаемый код

На интервью сначала предложите HashMap решение, затем можно упомянуть оптимизацию через массив для случая только английского алфавита.