Среден
проблем
Имате ключалка пред вас с 4 кръгли колела. Всяко колело има 10 слота: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'
. Колелата могат да се въртят свободно и да се увиват: например можем да превърнем '9'
в '0'
или '0'
в '9'
. Всяко движение се състои от завъртане на едно колело на един слот.
Заключването първоначално започва от '0000'
, низ, представляващ състоянието на 4-те колела.
Даден ви е списък от deadends
задънени улици, което означава, че ако ключалката покаже някой от тези кодове, колелцата на ключалката ще спрат да се въртят и вие няма да можете да я отворите.
Дадено е target
, представляващо стойността на колелата, които ще отключат ключалката, върнете минималния общ брой завъртания, необходими за отваряне на ключалката, или -1, ако е невъзможно.
Пример 1:
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202" Output: 6 Explanation: A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202". Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid, because the wheels of the lock become stuck after the display becomes the dead end "0102".
Пример 2:
Input: deadends = ["8888"], target = "0009" Output: 1 Explanation: We can turn the last wheel in reverse to move from "0000" -> "0009".
Пример 3:
Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888" Output: -1 Explanation: We can't reach the target without getting stuck.
Пример 4:
Input: deadends = ["0000"], target = "8888" Output: -1
Забележка:
- Дължината на
deadends
ще бъде в диапазона[1, 500]
. target
няма да бъде в списъкаdeadends
.- Всеки низ в
deadends
и низътtarget
ще бъде низ от 4 цифри от 10 000 възможности'0000'
до'9999'
.
Решение — едностранно BFS
Тъй като можем да променим само една цифра към нейното следващо/предишно число, този проблем трябва да бъде разрешен чрез подхода на BFS. Отбелязва се, че посетеният номер трябва да бъде записан в безизходици или ще бъде посетен отново. За съжаление, този подход ще достигне ограничението във времето в LeetCode.
Сложност
Тъй като знаем, че всички кандидати ще бъдат посетени след най-много 10 000 итерации, така че времевата сложност всъщност е O(10000) = O(1). Но ако броят на цифрите се увеличи от 4 на n
, неговата времева сложност ще стане O(10^n).
За пространствена сложност, тъй като има две посоки за въртене на цифри и има 4 цифри в тази ключалка, опашката трябва да поддържа до 8 елемента в нея. Следователно космическата сложност е O(2*4) = O(8) = O(1). И отново, ако броят на цифрите се увеличи от 4 до n
, неговата пространствена сложност ще стане O(2*n) = O(n).
Решение — Double Side BFS
Вместо да започваме само от „0000“, ние започваме и от „0000“ и насочваме и търсим техните съседи интерактивно. След като един номер влезе в посетен номер на друг, се намират най-кратките стъпки между тези два края.
Сложност
Времевата сложност и пространствената сложност са двойни спрямо едностранния подход, но все пак O(1)/O(10^n) и O(1)/O(n) съответно.