Рубрики

Найти все возможные интерпретации массива цифр

Рассмотрим систему кодирования для алфавитов в целые числа, где 'a' представлено как 1, 'b' как 2, .. 'z' как 26. Учитывая массив цифр (от 1 до 9) в качестве ввода, напишите функцию, которая печатает все допустимые интерпретации входного массива.

Примеры

Input: {1, 1}
Output: ("aa", 'k") 
[2 interpretations: aa(1, 1), k(11)]

Input: {1, 2, 1}
Output: ("aba", "au", "la") 
[3 interpretations: aba(1,2,1), au(1,21), la(12,1)]

Input: {9, 1, 8}
Output: {"iah", "ir"} 
[2 interpretations: iah(9,1,8), ir(9,18)]

Обратите внимание, что мы не можем изменить порядок массива. Это означает, что {1,2,1} не может стать {2,1,1}
На первый взгляд это выглядит как проблема перестановки / комбинации. Но при ближайшем рассмотрении вы поймете, что это интересная проблема дерева.
Идея в том, что строка может принимать не более двух путей:
1. Обработка одной цифры
2. Обработка двух цифр
Это означает, что мы можем использовать двоичное дерево здесь. Обработка с одной цифрой останется дочерней, а две цифры будут правой дочерней. Если значение двух цифр больше 26, тогда наш правый ребенок будет нулевым, поскольку у нас нет алфавита больше 26.

Давайте разберемся с примером .Array a = {1,2,1}. На диаграмме ниже показано, как растет наше дерево.

                           “” {1,2,1}            Codes used in tree
                       /             \               "a" --> 1
                      /               \              "b" --> 2 
                  "a"{2,1}            "l"{1}         "l" --> 12
                 /        \          /     \
                /          \        /       \
            "ab"{1}        "au"    "la"      null
             /    \
            /      \
         "aba"      null

В фигурных скобках {} содержится массив, ожидающий обработки. Обратите внимание, что с каждым уровнем размер нашего массива уменьшается. Если вы внимательно посмотрите, нетрудно обнаружить, что высота дерева всегда равна n (размер массива)
Как распечатать все строки (интерпретации)? Выходные строки являются листовым узлом дерева. т. е. для {1,2,1}, вывод равен {aba au la}.
Мы можем заключить, что в основном есть два шага, чтобы напечатать все интерпретации данного целочисленного массива.

Шаг 1: Создайте двоичное дерево со всеми возможными интерпретациями в конечных узлах.

Шаг 2: Распечатать все листовые узлы из двоичного дерева, созданного на шаге 1.

Ниже приводится реализация Java вышеупомянутого алгоритма.

// Java-программа для печати всех интерпретаций целочисленного массива

import java.util.Arrays;

  
// Узел двоичного дерева

class Node {

  

    String dataString;

    Node left;

    Node right;

  

    Node(String dataString) {

        this.dataString = dataString;

        // По умолчанию левый и правый дочерние элементы равны нулю.

    }

  

    public String getDataString() {

        return dataString;

    }

}

  

public class arrayToAllInterpretations {

  

    // Метод создания двоичного дерева, в котором хранятся все интерпретации

    // из arr [] в ведущих узлах

    public static Node createTree(int data, String pString, int[] arr) {

  

        // Неверный ввод в виде букв алфавита от 1 до 26

        if (data > 26

            return null;

  

        // Родительская строка + строка для этого узла

        String dataToStr = pString + alphabet[data];

  

        Node root = new Node(dataToStr);

  

        // если arr.length равен 0, значит, мы закончили

        if (arr.length != 0) {

            data = arr[0];

  

            // новый массив будет от индекса 1 до конца, так как мы потребляем

            // первый индекс с этим узлом

            int newArr[] = Arrays.copyOfRange(arr, 1, arr.length);

  

            // левый ребенок

            root.left = createTree(data, dataToStr, newArr);

  

            // правый потомок будет нулевым, если размер массива равен 0 или 1

            if (arr.length > 1) {

  

                data = arr[0] * 10 + arr[1];

  

                // новый массив будет от индекса 2 до конца, как мы

                // потребляем первые два индекса с этим узлом

                newArr = Arrays.copyOfRange(arr, 2, arr.length);

  

                root.right = createTree(data, dataToStr, newArr);

            }

        }

        return root;

    }

  

    // Распечатать листовые узлы

    public static void printleaf(Node root) {

        if (root == null

            return;

  

        if (root.left == null && root.right == null

            System.out.print(root.getDataString() + "  ");

          

        printleaf(root.left);

        printleaf(root.right);

    }

  

    // Основная функция, которая печатает все интерпретации массива

    static void printAllInterpretations(int[] arr) {

  

        // Шаг 1: Создать дерево

        Node root = createTree(0, "", arr);

  

        // Шаг 2: Распечатать листовые узлы

        printleaf(root);

  

        System.out.println();  // Распечатать новую строку

    }

  

    // Для простоты я беру это как строковый массив. Char Array сэкономит место

    private static final String[] alphabet = {"", "a", "b", "c", "d", "e",

        "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r",

        "s", "t", "u", "v", "w", "x", "v", "z"};

  

    // Метод драйвера для тестирования вышеуказанных методов

    public static void main(String args[]) {

  

        // AACD (1,1,3,4) AMD (1,13,4) KCD (11,3,4)

        // Примечание: 1,1,34 недопустимо, так как у нас нет значений, соответствующих

        // до 34 в алфавите

        int[] arr = {1, 1, 3, 4};

        printAllInterpretations(arr);

  

        // ааа (1,1,1) ак (1,11) ка (11,1)

        int[] arr2 = {1, 1, 1};

        printAllInterpretations(arr2);

  

        // bf (2,6) z (26)

        int[] arr3 = {2, 6};

        printAllInterpretations(arr3);

  

        // ab (1,2), l (12)

        int[] arr4 = {1, 2};

        printAllInterpretations(arr4);

  

        // a (1,0} j (10)

        int[] arr5 = {1, 0};

        printAllInterpretations(arr5);

  

        // "" вывод пустой строки, так как массив пуст

        int[] arr6 = {};

        printAllInterpretations(arr6);

  

        // abba abu ava lba lu

        int[] arr7 = {1, 2, 2, 1};

        printAllInterpretations(arr7);

    }

}

Выход:

aacd  amd  kcd  
aaa  ak  ka  
bf  z  
ab  l  
a  j  
  
abba  abu  ava  lba  lu  

Упражнение:
1. Какова временная сложность этого решения? [Подсказка: размер дерева + поиск узлов листа]
2. Можем ли мы хранить конечные узлы во время создания дерева, чтобы не нужно было повторять цикл для выборки конечных узлов?
3. Как мы можем уменьшить дополнительное пространство?

Эта статья составлена Варуном Джайном . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найти все возможные интерпретации массива цифр

0.00 (0%) 0 votes