Нужно сделать метод, который определяет, можно ли из букв двух строк собрать одну строку. Решение вроде правильное, но не понятно - почему не проходит

Question

public class Solution {
    public static void main(String[] args) {
        System.out.println(isMerge("codewars", "cdwr", "oeas"));
    }
    public static boolean isMerge(String s, String part1, String part2) {
        boolean merge = false;
        char[] sc = s.toCharArray();
        boolean[] sch = new boolean[s.length()];
        for (int i = 0; i < sch.length; i++) {
            sch[i] = loll(sc[i], part1, part2);
        }
        for (int i = 0; i < sch.length; i++) {
            if (!sch[i]) {
                break;
            }
        }
        return merge;
    }
    public static boolean loll(char h, String part1, String part2) {
        String sum = part1 + part2;
        char[] sumArr = sum.toCharArray();
        for (int i = 0; i < sumArr.length; i++) {
            if (h == sumArr[i]) {
                return true;
            }
        }
        return false;
    }
}

Answer 1

Баг в том, что значение флажка merge в методе isMerge сразу устанавливается в false и никогда больше не переприсваивается, независимо от содержимого массива sch.

В принципе этот флажок не особо нужен, и код можно исправить:

    public static boolean isMerge(String s, String part1, String part2) {
        char[] sc = s.toCharArray();
        boolean[] sch = new boolean[s.length()];
        for (int i = 0; i < sch.length; i++) {
            sch[i] = loll(sc[i], part1, part2);
        }
        System.out.println(Arrays.toString(sch));
        for (int i = 0; i < sch.length; i++) {
            if (!sch[i]) {
                return false;
            }
        }
        return true;
    }

Следует также заметить, что данное решение неустойчиво к наличию дублированных букв:

System.out.println(isMerge("helloworld", "helo", "wrd")); // -> true

Более надежное решение состоит в том, чтобы подсчитать и сравнить частоты букв в заданной строке и в сумме двух подстрок. Если будет обнаружена "нехватка" (или "излишек") букв, то слияние будет невозможно.

Для упрощенного алфавита (только английские/латинские) буквы можно взять массив, в более общем случае для подсчёта частот можно воспользоваться хэш-таблицей.

Также можно для начала сравнить длины строк, если будет обнаружено неравенство, дальнейшая проверка не имеет значения.

public static boolean isMerge(String s, String part1, String part2) {
    if (s.length () != part1.length() + part2.length()) {
        return false;
    }

    int[] freqs = new int[26];
    for (char c : s.toLowerCase().toCharArray()) {
        freqs[c - 'a']++;
    }
    for (char c : (part1 + part2).toLowerCase().toCharArray()) {
        freqs[c - 'a']--;
    }
    
    for (int i = 0; i < freqs.length; i++) {
        if (freqs[i] != 0) {
            return false;
        }
    }
    return true;
}

БЛОГ НА HUSL

Нужно сделать метод, который определяет, можно ли из букв двух строк собрать одну строку. Решение вроде правильное, но не понятно - почему не проходит

Ответы (1 шт):