Skip to content

10.05. Sparse Array Search

Description

Given a sorted array of strings that is interspersed with empty strings, write a method to find the location of a given string.

Example1:

 Input: words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ta"

 Output: -1

 Explanation: Return -1 if s is not in words.

Example2:

 Input: words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ball"

 Output: 4

Note:

  1. 1 <= words.length <= 1000000

Solutions

Thinking

A sorted string array is punctuated by empties. Binary search still works after skipping blanks, but a midpoint that is empty needs extra probing.

The code uses the same divide-and-conquer as the magic-index problem: search the left half first (leftmost hit), then the mid, then the right. Empty strings simply fail the equality test.

The worst case is linear, yet the left-first order returns the leftmost match without special-casing empties.

We design a function \(dfs(i, j)\) to find the target string in the array \(nums[i, j]\). If found, return the index of the target string, otherwise return \(-1\). So the answer is \(dfs(0, n-1)\).

The implementation of the function \(dfs(i, j)\) is as follows:

  1. If \(i > j\), return \(-1\).
  2. Otherwise, we take the middle position \(mid = (i + j) / 2\), then recursively call \(dfs(i, mid-1)\). If the return value is not \(-1\), it means that the target string is found in the left half, return it directly. Otherwise, if \(words[mid] = s\), it means that the target string is found, return it directly. Otherwise, recursively call \(dfs(mid+1, j)\) and return.

In the worst case, the time complexity is \(O(n \times m)\), and the space complexity is \(O(n)\). Where \(n\) and \(m\) are the length of the string array and the length of the string \(s\), respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def findString(self, words: List[str], s: str) -> int:
        def dfs(i: int, j: int) -> int:
            if i > j:
                return -1
            mid = (i + j) >> 1
            l = dfs(i, mid - 1)
            if l != -1:
                return l
            if words[mid] == s:
                return mid
            return dfs(mid + 1, j)

        return dfs(0, len(words) - 1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int findString(String[] words, String s) {
        return dfs(words, s, 0, words.length - 1);
    }

    private int dfs(String[] words, String s, int i, int j) {
        if (i > j) {
            return -1;
        }
        int mid = (i + j) >> 1;
        int l = dfs(words, s, i, mid - 1);
        if (l != -1) {
            return l;
        }
        if (words[mid].equals(s)) {
            return mid;
        }
        return dfs(words, s, mid + 1, j);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findString(vector<string>& words, string s) {
        function<int(int, int)> dfs = [&](int i, int j) {
            if (i > j) {
                return -1;
            }
            int mid = (i + j) >> 1;
            int l = dfs(i, mid - 1);
            if (l != -1) {
                return l;
            }
            if (words[mid] == s) {
                return mid;
            }
            return dfs(mid + 1, j);
        };
        return dfs(0, words.size() - 1);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func findString(words []string, s string) int {
    var dfs func(i, j int) int
    dfs = func(i, j int) int {
        if i > j {
            return -1
        }
        mid := (i + j) >> 1
        if l := dfs(i, mid-1); l != -1 {
            return l
        }
        if words[mid] == s {
            return mid
        }
        return dfs(mid+1, j)
    }
    return dfs(0, len(words)-1)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function findString(words: string[], s: string): number {
    const dfs = (i: number, j: number): number => {
        if (i > j) {
            return -1;
        }
        const mid = (i + j) >> 1;
        const l = dfs(i, mid - 1);
        if (l !== -1) {
            return l;
        }
        if (words[mid] === s) {
            return mid;
        }
        return dfs(mid + 1, j);
    };
    return dfs(0, words.length - 1);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    func findString(_ words: [String], _ s: String) -> Int {
        return dfs(words, s, 0, words.count - 1)
    }

    private func dfs(_ words: [String], _ s: String, _ i: Int, _ j: Int) -> Int {
        if i > j {
            return -1
        }
        let mid = (i + j) >> 1
        let left = dfs(words, s, i, mid - 1)
        if left != -1 {
            return left
        }
        if words[mid] == s {
            return mid
        }
        return dfs(words, s, mid + 1, j)
    }
}

Comments