Solve palindrome pairs and key path
Company: Airbnb
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Question
LeetCode 336. Palindrome Pairs; LeetCode 864. Shortest Path to Get All Keys
https://leetcode.com/problems/palindrome-pairs/description/ https://leetcode.com/problems/shortest-path-to-get-all-keys/description/
Quick Answer: This pair of problems evaluates proficiency with string-processing algorithms and advanced data structures for matching, alongside state-space graph search techniques and state-encoding strategies.
You are given an m x n grid of characters representing a maze. The grid contains exactly one start cell '@', walls '#', empty cells '.', lowercase keys 'a' to 'f', and uppercase locks 'A' to 'F'. You can move up, down, left, or right by one cell per step. You can pass through a lock only if you have collected its corresponding key (e.g., key 'a' opens lock 'A'). Collecting a key adds it to your set permanently. Return the minimum number of steps required to collect all keys present in the grid. If it is impossible, return -1. If there are no keys, return 0.
Constraints
- 1 <= m, n <= 30
- Grid size m * n <= 900
- Grid characters are '@', '#', '.', 'a'-'f', 'A'-'F' only
- Exactly one start cell '@'
- At most 6 distinct keys ('a'..'f')
- Movement allowed in 4 directions (up, down, left, right) with cost 1 per step
- You cannot move outside the grid or into walls '#'
Solution
from typing import List
from collections import deque
def shortest_path_all_keys(grid: List[str]) -> int:
m = len(grid)
n = len(grid[0]) if m > 0 else 0
start = (-1, -1)
all_keys_mask = 0
for r in range(m):
for c in range(n):
ch = grid[r][c]
if ch == '@':
start = (r, c)
elif 'a' <= ch <= 'f':
all_keys_mask |= 1 << (ord(ch) - ord('a'))
# If no keys to collect, steps are 0
if all_keys_mask == 0:
return 0
sr, sc = start
q = deque([(sr, sc, 0, 0)]) # r, c, keys_mask, dist
visited = set([(sr, sc, 0)])
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while q:
r, c, keys, dist = q.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if not (0 <= nr < m and 0 <= nc < n):
continue
cell = grid[nr][nc]
if cell == '#':
continue
next_keys = keys
if 'A' <= cell <= 'F':
# Need corresponding key bit to pass
if not (keys & (1 << (ord(cell) - ord('A')))):
continue
if 'a' <= cell <= 'f':
next_keys = keys | (1 << (ord(cell) - ord('a')))
if next_keys == all_keys_mask:
return dist + 1
state = (nr, nc, next_keys)
if state not in visited:
visited.add(state)
q.append((nr, nc, next_keys, dist + 1))
return -1
Explanation
Perform BFS over an augmented state space (row, col, keyMask). The keyMask records which keys have been collected using bits. Precompute the target mask by scanning the grid. From each state, explore four neighbors if within bounds and not a wall. You may pass a lock only if the corresponding key bit is set. When moving onto a key cell, set its bit in the mask; if this equals the target mask, return the steps taken so far plus one. Use a visited set keyed by (row, col, keyMask) to prevent revisiting states. BFS guarantees the first time all keys are collected is optimal.
Time complexity: O(m * n * 2^k), where k <= 6 is the number of distinct keys. Space complexity: O(m * n * 2^k) for the visited state set and BFS queue.
Hints
- Use BFS where each state is (row, col, keyMask).
- Represent collected keys with a bitmask; bit i corresponds to key chr(ord('a')+i).
- Precompute the target key mask by scanning the grid.
- Maintain visited states by (row, col, keyMask) to avoid revisiting.
- When encountering a lock 'A'-'F', ensure the corresponding bit is set in keyMask before moving through.