Stepik - 4.2. Расшифровка Кодов Хаффмана
Описание задачи
Восстановите строку по её коду и беспрефиксному коду символов.
В первой строке входного файла заданы два целых числа 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());
}
}