Java: Решение задачи с реального кодинг интервью

Ранее в статье мы приводили пример реальной задачи с кодинг интервью.

Теперь пришло время разобрать ее решение!

На первый взгляд задача кажется сложной. Любая буква первой строки может быть приобразована в любую букву второй строки. Как же подойти к решению такой задачи?

А подойти к решению надо с более тщательного изучения требований!

Если вдуматься в третье правило задания, которое говорит о том, что позиция буквы из первой строки должна совпадать с позицией буквы из второй строки в которую она преобразовывается то все становится гораздо проще! Любая буква первой строки не может быть преобразована в любую букву второй строки, она может быть преобразована только в букву второй строки стоящую на той же позиции. Теперь мы можем просто применить проход по первой строки слева на право и нам понятно какую букву надо преобразовывать в какую.

Остаётся вопрос следующий: как запоминать какую букву первой строки мы преобразовали в какую букву второй строки? Это нужно, потому что буквы в строке могут повторяться. Одинаковые буквы первой строки должны быть преобразованы в одинаковые буквы второй строки.

Для запоминания какая буква первой строки была преобразована в какую букву второй строки можно использовать структуру данных Map! Тогда ключём в мапе будет буква первой строки, а значением буква второй строки.

Структур данных Map понадобится две! Одна для запоминания маппинга букв первой строки во вторую, второя мапа для запоминания маппинга букв второй строки в буквы первой.

Полное решение задачи с тестовыми примерами приведено ниже:

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

public class StringConvert {

public static void main(String[] args) {
System.out.println(«egg, add = » + canBeConverted(«egg», «add»));
System.out.println(«egd, add = » + canBeConverted(«egd», «add»));
System.out.println(«egg, adc = » + canBeConverted(«egg», «adc»));
System.out.println(«abc, xyz = » + canBeConverted(«abc», «xyz»));
}

public static boolean canBeConverted(String str1, String str2) {
Map<Character, Character> firstToSecond = new HashMap<>();
Map<Character, Character> secondToFirst = new HashMap<>();

for (int i = 0; i < str1.length(); i++) {
char firstChar = str1.charAt(i);
char secondChar = str2.charAt(i);

if (firstToSecond.containsKey(firstChar)) {
char firstMappedTo = firstToSecond.get(firstChar);
if (firstMappedTo != secondChar) {
return false;
}
} else {
firstToSecond.put(firstChar, secondChar);
}

if (secondToFirst.containsKey(secondChar)) {
char secondMappedTo = secondToFirst.get(secondChar);
if (secondMappedTo != firstChar) {
return false;
}
} else {
secondToFirst.put(secondChar, firstChar);
}

}

return true;
}

}

Удалось ли вам самостоятельно решить эту задачу?