Описание задачи

Восстановите строку по её коду и беспрефиксному коду символов.

В первой строке входного файла заданы два целых числа k и l через пробел — количество различных букв, встречающихся в строке, и размер получившейся закодированной строки, соответственно. В следующих k строках записаны коды букв в формате “letter: code”. Ни один код не является префиксом другого. Буквы могут быть перечислены в любом порядке. В качестве букв могут встречаться лишь строчные буквы латинского алфавита; каждая из этих букв встречается в строке хотя бы один раз. Наконец, в последней строке записана закодированная строка. Исходная строка и коды всех букв непусты. Заданный код таков, что закодированная строка имеет минимальный возможный размер.

В первой строке выходного файла выведите строку s. Она должна состоять из строчных букв латинского алфавита. Гарантируется, что длина правильного ответа не превосходит 10^4 символов.

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

/**
 * Main
 *
 * @author Vladislav Sidlyarevich <vlsidlyarevich@gmail.com>
 * Created on 5/2/21.
 */
public class Main {

    public static void main(String[] args) {
        Main main = new Main();
        main.run();
    }

    public void run() {
        Scanner scanner = new Scanner(System.in).useDelimiter("\n");
        String[] input = scanner.nextLine().split("\\s+");
        int numberOfUniqueLetters = Integer.parseInt(input[0]);
        int codeSize = Integer.parseInt(input[1]);

        Map<String, Character> codes = new HashMap<>();

        for (int i = 0; i < numberOfUniqueLetters; i++) {
            String[] code = scanner.nextLine().split("\\s+");
            codes.put(code[1], code[0].charAt(0));
        }

        String encodedInput = scanner.nextLine();

        StringBuilder decodedInput = new StringBuilder();
        String stack = "";

        //Decode the input
        for(Character ch : encodedInput.toCharArray()) {
            stack += ch;
            if(codes.containsKey(stack)) {
                decodedInput.append(codes.get(stack));
                stack = "";
            }
        }

        System.out.println(decodedInput.toString());
    }
}