Solve palindrome pairs and key path

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/

Shortest Path to Collect All Keys

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

Examples

Example 1

Input: grid = ["@.a.#","###.#","b.A.B"]
Output: 8

Explanation: One shortest route collects 'a' then 'b' in 8 steps while navigating around walls and using the key to pass the lock 'A'.

Example 2

Input: grid = ["@..aA","..B#.","....b"]
Output: 6

Explanation: Collect 'a' and 'b' in 6 steps. The lock 'A' is passable after picking up 'a'.

Hints

1. Use BFS where each state is (row, col, keyMask).
2. Represent collected keys with a bitmask; bit i corresponds to key chr(ord('a')+i).
3. Precompute the target key mask by scanning the grid.
4. Maintain visited states by (row, col, keyMask) to avoid revisiting.
5. When encountering a lock 'A'-'F', ensure the corresponding bit is set in keyMask before moving through.

Approach

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