Java практика. Решаем задачи с Codewars

Комбинации слов, образованные заменой данных цифр соответствующими алфавитами

Для заданного набора положительных чисел найти все возможные комбинации слов, образованные заменой цифр соответствующими символами английского алфавита, т. е. подмножество {1} можно заменить на A, {2} можно заменить на B, {1, 0}  можно заменить на J, {2, 1} можно заменить на U, так далее.

Для каждого i-того элемент, есть две возможности – либо этот i тый элемент будет суммироваться со следующимс (i+1) элементом, если число, образованное ими меньше 26 (кол-во букв в английском алфавите) или iый элемент формирует новый символ сам по себе.

@javatg – практика java в телеграмме.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Main
{
    private static final String alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
 
    // Функция для поиска всех возможных комбинаций слов, образованных
    // путем замены заданных положительных чисел на соответствующие
    // символы английского алфавита
    public static void recur(int[] digits, int i, String str)
    {
        // базовый вариант: все цифры обрабатываются в текущей конфигурации
        if (i == digits.length)
        {
            // напечатать строку
            System.out.println(str);
            return;
        }
 
        int sum = 0;
 
        // обрабатываем следующие две цифры (i-ю и (i+1)-ю)
        for (int j = i; j <= Integer.min(i + 1, digits.length - 1); j++)
        {
            sum = (sum * 10) + digits[j];
 
            // если допустимый символ можно сформировать, взяв одну или обе цифры,
            // добавляем его к выводу и повторяем для оставшихся цифр
            if (sum > 0 && sum <= 26) {
                recur(digits, j + 1, str + alphabet.charAt(sum - 1));
            }
        }
    }
 
    public static void findCombinations(int[] digits)
    {
        // базовый вариант
        if (digits == null || digits.length == 0) {
            return;
        }
 
        String str = "";
        recur(digits, 0, str);
    }
 
    public static void main(String[] args)
    {
        int[] digits = { 1, 2, 2 };
 
        findCombinations(digits);
    }
}
результат:

A B C D +E F G -H +I J -Q +K +R +X +Y Z

Мы также можем решить эту проблему, используя двоичное дерево и рекурсию. Основная идея остается той же, т. е. повторить с оставшимися цифрами, рассматривая обе возможности для каждого числа. i'th элемент ввода – либо этот i'th элемент будет сочетаться с (i+1)'th элемента, если число, образованное ими, меньше, чем равно 26 или же i'th сам элемент сформирует новый символ.

Единственное отличие состоит в том, что вместо строки для хранения вывода используйте узлы двоичного дерева.

// Класс для хранения узла бинарного дерева
class Node
{
    String key;
    Node left, right;
 
    // Конструктор
    Node(String key)
    {
        this.key = key;
        left = right = null;
    }
}
 
class Main
{
    private static final String alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
 
    // Функция для печати всех листовых узлов бинарного дерева
    public static void print(Node node)
    {
        if (node == null) {
            return;
        }
 
        if (node.left == null && node.right == null) {
            System.out.print(node.key + " ");
        }
        else {
            print(node.right);
            print(node.left);
        }
    }
 
    // Функция для построения бинарного дерева, в котором каждый конечный узел содержит
    // образована одна уникальная комбинация слов
    public static void construct(Node root, int[] digits, int i)
    {
        // Базовый случай: пустое дерево
        if (root == null || i == digits.length) {
            return;
        }
 
        // проверяем, существует ли `digits[i+1]`
        if (i + 1 < digits.length)
        {
            // обрабатываем текущую и следующую цифру
            int sum = 10 * digits[i] + digits[i + 1];
 
            // если обе цифры могут образовывать допустимый символ, создаем из него левого потомка
            if (sum <= 26) {
                root.left = new Node(root.key + alphabet.charAt(sum - 1));
            }
 
            // строим левое поддерево по оставшимся цифрам
            construct(root.left, digits, i + 2);
        }
 
        // обрабатываем текущую цифру и создаем из нее нужного потомка
        root.right = new Node(root.key + alphabet.charAt(digits[i] - 1));
 
        // строим правое поддерево по оставшимся цифрам
        construct(root.right, digits, i + 1);
    }
 
    public static void main(String[] args)
    {
        int[] digits = { 1, 2, 2, 1 };
 
        // создаем пустой корень
        Node root = new Node("");
 
        // построить бинарное дерево
        construct(root, digits, 0);
 
        print(root);
    }
}

результат:

ABBA ABU AVA LBA LU

Временная сложность обоих рассмотренных выше методов экспоненциальна и требует дополнительного места для рекурсии (стека вызовов).