Solve string match and DashMart BFS

Question

Implement a string-matching function that returns the first index of a pattern in a text (akin to LeetCode 28 Implement strStr()). 2) “Dash Mart” grid path-finding: given a 2-D map with a start cell, obstacles, and target pickup cells, code a BFS to find the minimum steps to collect all required items and explain follow-up optimizations.

https://leetcode.com/problems/implement-strstr/description/

Implement strStr()

Implement a string-matching function strStr(haystack, needle) that returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. This is the classic LeetCode 28 problem.

By convention, when needle is the empty string, return 0 (the empty string is found at the start of any string).

Examples:

• strStr("sadbutsad", "sad") = 0 ("sad" occurs at index 0 and 6; first is 0)
• strStr("leetcode", "leeto") = -1 ("leeto" does not occur)
• strStr("hello", "ll") = 2

A brute-force O(n*m) scan is acceptable for the interview; mention KMP / Rabin-Karp as the O(n+m) follow-up.

Constraints

• 1 <= haystack.length, needle.length <= 10^4 (and needle may be empty by the convention above)
• haystack and needle consist of only lowercase English characters
• Return 0 when needle is the empty string

Hints

1. Slide a window of length len(needle) across haystack and compare substrings.
2. Short-circuit: if len(needle) > len(haystack), the answer is immediately -1.
3. For the optimal O(n+m) follow-up, precompute the KMP failure (longest-proper-prefix-suffix) table so you never re-examine matched characters.

DashMart Grid: Minimum Steps to Collect All Items (BFS)

You are given a 2-D grid representing a DashMart store floor. Each cell holds one of:

• 0 = open walkable cell
• 1 = obstacle (a shelf you cannot enter)
• 2 = the start cell (exactly one)
• 3 = a pickup cell holding a required item

Starting from the 2 cell, you may move one step up, down, left, or right into any non-obstacle cell (steps cost 1 each). Return the minimum number of steps needed to visit every 3 cell (collect every required item), in any order. Return -1 if it is impossible to collect them all, and 0 if there are no items to collect (or all items coincide with the start).

Because you must collect all items and may need to backtrack, this is a multi-target shortest-path problem. The standard approach is a BFS over the state (row, col, collected_bitmask): the position plus a bitmask of which items have been picked up so far. The first time the bitmask becomes full, the current distance is the answer.

Follow-up optimizations to discuss: precompute pairwise shortest distances between start and all items with per-source BFS, then solve a Traveling-Salesman-style DP over the item set (Held-Karp, O(k^2 * 2^k)) — far cheaper than state-BFS when the grid is huge but the number of items k is small.

Constraints

• 1 <= rows, cols <= 50
• Exactly one start cell (value 2); 0 or more item cells (value 3)
• k (number of items) is small (e.g. <= 10) so 2^k stays tractable
• Movement is 4-directional into non-obstacle cells only

Examples

Example 1

Input: ([[2, 0, 3]],)
Output: 2

Explanation: Start at (0,0), one item at (0,2). Walk right twice: 2 steps.

Example 2

Input: ([[2, 1, 3]],)
Output: -1

Explanation: The obstacle at (0,1) walls off the item at (0,2); it can never be reached, so -1.

Hints

1. Encode progress as a bitmask: bit i is set once item i has been visited. The goal state is the all-ones mask.
2. BFS over states (row, col, mask) — not just (row, col) — because you may legitimately revisit a cell with a different set of items already collected.
3. The first time you reach the full mask, the BFS distance is optimal (all edges cost 1).
4. Follow-up: if the grid is huge but items are few, run one BFS from start and from each item to get pairwise distances, then solve a small Held-Karp TSP DP over the items instead of a grid-sized state space.