Правильно ли это решение для решения перестановки строк CTCI?

Question

Кажется, работает, и я не могу найти никого с похожим ответом. Это настолько прямолинейно - я скептически настроен.

public static boolean permutation(String s, String t) {
    if (s.length() != t.length()) return false; // Permutations must be same length

    int sum = 0;

    for(char c : s.toCharArray())
        sum += c - 'a';

    for(char c : t.toCharArray())
        sum -= c - 'a';

    return sum == 0;
}

Кроме того, временная сложность - O (n), а пространственная сложность - O (1), верно ??

Answer 1

Нет, вы не должны принимать решение из-за суммы, потому что если вы попробуете это permutation("CTCI", "CCCZ"), получите true из-за той же суммы

вы можете проверить это, если вам нужен алгоритм в O(N)

   public static boolean permutation(String s, String t) {
        if (s.length() != t.length())
            return false;

        int[] freq = new int[26];

        for (int i = 0; i < s.length(); i++) {
            freq[s.charAt(i) % 26]++;
            freq[t.charAt(i) % 26]--;
        }

        for (int i = 0; i < freq.length; i++) {
            if (freq[i] != 0)
                return false;
        }

        return true;
    }