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 '#'
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.