Я занимался вопросами подготовки к интервью, и это вопрос, с которым у меня были проблемы, поскольку я не знаю, как реализовать это решение. Итак, вот настройка. Вам дается 8x8 сетка букв и список слов, и вы должны вернуть самое длинное слово в списке, которое может быть сформировано, начиная с буквы на сетке, а затем перемещаясь по сетке так, чтобы рыцарь в шахматы. Например, если у вас список [ «слово», «строка», «тест»] и следующая сетка:Интервью Prep Words in a Grid
Y W E Z T N U W
O P A A C Q G F
T E L Z X C V B
N M M W F R T O
U I O N A S D F
B E J O L Z V C
T B N M Q W E R
T A S G X Z R S
Тогда ты вернешься «тест», потому что это может быть сформировано, начиная с нижний левый угол сетки для «T», прыгая вверх два и вправо, чтобы получить «E», прыгая вниз по двум и правым, чтобы получить «S», а затем оставил два и один, чтобы получить ' T ', и никакие другие слова не могут быть сформированы на этой сетке.
Я думаю, вы бы использовали алгоритм ветвления и привязки, но я полностью потерял, как это установить. Может ли кто-нибудь помочь? Я пытаюсь реализовать в python.
Примечание: буквы могут повторяться в сетке, то есть вы можете прыгать на одну букву столько раз, сколько хотите.