BFS on string

Question

Implement a breadth-first search (BFS) algorithm to find the shortest path in a given string where each character represents a node. The input will be a string of lowercase letters, and the output should be the length of the shortest path from the first character to the last character, considering each character can only transition to its adjacent characters.

Codemia · Accepted Answer

The problem requires us to find the shortest path in a string where each character represents a node, and movements can only occur to adjacent characters. Given the nature of the problem, a Breadth-First Search (BFS) approach is suitable here because BFS explores all neighbors at the present depth prior to moving on to nodes at the next depth level. This characteristic is ideal for determining the shortest path in an unweighted graph, which we can model the string as.

1. **Initialize a queue:** Start by placing the first character's index (0) in a queue and a set to track visited indices.
2. **Breadth-First Search Loop:** While the queue is not empty, do the following:
   - Dequeue the front element (current index).
   - If the current index is the last index of the string, return the path length (which will be the depth level).
   - Check the adjacent indices (current index - 1 and current index + 1) to see if they are valid (within bounds and not visited).
   - If valid, mark them as visited and enqueue them.
3. **End condition:** If the queue is exhausted without finding the last index, return -1 (indicating no path exists).

**Example:** For the input string 'abcde', the BFS would progress as follows:
- Start with index 0 ('a'). Queue: [0].
- Dequeue 0: Visit 'a'. Enqueue 1: Queue: [1].
- Dequeue 1: Visit 'b'. Enqueue 0 (already visited, ignore), 2: Queue: [2].
- Dequeue 2: Visit 'c'. Enqueue 1 (already visited, ignore), 3: Queue: [3].
- Continue until reaching index 4 ('e').

```python
from collections import deque

def shortest_path(s: str) -> int:
    if not s:
        return -1  # Edge case: empty string
    if len(s) == 1:
        return 0  # Edge case: single character

queue = deque([0])  # Start from first character index
    visited = set([0])  # Track visited indices
    steps = 0  # Initialize the path length

while queue:
        for _ in range(len(queue)):
            current_index = queue.popleft()
            if current_index == len(s) - 1:
                return steps  # Found last character

# Check the left adjacent
            if current_index - 1 >= 0 and (current_index - 1) not in visited:
                visited.add(current_index - 1)
                queue.append(current_index - 1)
            # Check the right adjacent
            if current_index + 1 < len(s) and (current_index + 1) not in visited:
                visited.add(current_index + 1)
                queue.append(current_index + 1)
        steps += 1  # Increment depth level

return -1  # No path found
```

The time complexity of this BFS solution is O(n), where n is the length of the string. This is because each character (node) is processed at most once. The space complexity is also O(n) in the worst case, where we may need to store all indices in the queue and the visited set.

1. **Empty String:** Input `''` should return -1 as there is no path to traverse.
2. **Single Character:** Input `'a'` should return 0 since no movement is required.
3. **Two Characters:** Input `'ab'` should return 1 since the only path is from index 0 to 1. 
4. **Long String with No Path:** An input like `'aaaaaa'`, where all characters are the same, should return -1 if the last character is unreachable via valid moves.

BFS on string

Coinbase

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Coinbase Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string