Ранее в статье мы приводили пример реальной задачи с кодинг интервью.
Теперь пришло время разобрать ее решение!
На первый взгляд задача кажется сложной. Любая буква первой строки может быть приобразована в любую букву второй строки. Как же подойти к решению такой задачи?
А подойти к решению надо с более тщательного изучения требований!
Если вдуматься в третье правило задания, которое говорит о том, что позиция буквы из первой строки должна совпадать с позицией буквы из второй строки в которую она преобразовывается то все становится гораздо проще! Любая буква первой строки не может быть преобразована в любую букву второй строки, она может быть преобразована только в букву второй строки стоящую на той же позиции. Теперь мы можем просто применить проход по первой строки слева на право и нам понятно какую букву надо преобразовывать в какую.
Остаётся вопрос следующий: как запоминать какую букву первой строки мы преобразовали в какую букву второй строки? Это нужно, потому что буквы в строке могут повторяться. Одинаковые буквы первой строки должны быть преобразованы в одинаковые буквы второй строки.
Для запоминания какая буква первой строки была преобразована в какую букву второй строки можно использовать структуру данных 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;
}
}
Удалось ли вам самостоятельно решить эту задачу?