Solve DFS grid and keypad problems

You may be asked to solve one or more DFS/backtracking problems:

1. Grid connectivity problem: Given an m x n grid where 1 represents land and 0 represents water, count how many connected land regions exist. Cells are connected horizontally and vertically.

2. Phone keypad combinations: On a classic phone keypad, digits map to letters as follows: 2 -> abc, 3 -> def, 4 -> ghi, 5 -> jkl, 6 -> mno, 7 -> pqrs, 8 -> tuv, 9 -> wxyz.

   • Given a digit string such as 2345, generate all possible letter strings it can represent.
   • Also determine how many possible outputs exist for the input.

Explain your approach, edge cases, and time/space complexity.

Part 1: Count Connected Land Regions

You are given a 2D binary grid where 1 represents land and 0 represents water. Count how many connected land regions exist. Two land cells belong to the same region if they are connected horizontally or vertically. Diagonal cells are not connected.

Constraints

• 0 <= number of rows <= 200
• 0 <= number of columns <= 200
• Each grid cell is either 0 or 1
• All rows have the same length

Examples

Example 1

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

Explanation: There are three separate land regions: the top-left cluster, the right-side vertical cluster, and the single land cell at the bottom-left.

Example 2

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

Explanation: There is no land in the grid.

Hints

1. Whenever you find an unvisited land cell, start a DFS or BFS from it and mark every reachable land cell.
2. Increase the region count only when you begin exploring a brand-new land component.

Part 2: Generate Phone Keypad Letter Combinations

On a classic phone keypad, digits map to letters as follows: 2 -> abc, 3 -> def, 4 -> ghi, 5 -> jkl, 6 -> mno, 7 -> pqrs, 8 -> tuv, 9 -> wxyz. Given a string of digits containing only characters from '2' to '9', return all possible letter combinations the number can represent. Return the combinations in the natural backtracking order: process digits from left to right, and for each digit, try its letters in listed order. If the input is empty, return an empty list.

Constraints

• 0 <= len(digits) <= 10
• Each character in digits is between '2' and '9'
• The returned order should follow keypad letter order from left to right

Examples

Example 1

Input: ('23',)
Output: ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

Explanation: Digit '2' gives abc and digit '3' gives def, so there are 3 x 3 = 9 combinations.

Example 2

Input: ('',)
Output: []

Explanation: An empty input has no combinations.

Hints

1. Think of each digit as a set of choices. Build the answer one position at a time.
2. A recursive backtracking function can append one letter, explore deeper, then remove it to try the next letter.

Part 3: Count Phone Keypad Output Possibilities

Using the same phone keypad mapping—2 -> abc, 3 -> def, 4 -> ghi, 5 -> jkl, 6 -> mno, 7 -> pqrs, 8 -> tuv, 9 -> wxyz—determine how many distinct letter strings a given digit string can represent. Do not generate the actual strings. If the input is empty, return 0.

Constraints

• 0 <= len(digits) <= 100000
• Each character in digits is between '2' and '9'
• The answer may be very large; in Python, normal integers can handle it

Examples

Example 1

Input: ('2345',)
Output: 81

Explanation: Each of these four digits maps to 3 letters, so the total is 3 x 3 x 3 x 3 = 81.

Example 2

Input: ('',)
Output: 0

Explanation: An empty input has no possible outputs.

Hints

1. Each digit contributes an independent number of choices: usually 3, but 7 and 9 contribute 4.
2. The total count is the product of the number of choices for each digit.