How to Compute Shortest Distance to a Character in a String?

Given a string S and a character C, return an array of integers representing the shortest distance from the character C in the string.
Example: Input: S = “loveleetcode”, C = ‘e’. Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

• S string length is in [1, 10000].
• C is a single character, and guaranteed to be in string S.
• All letters in S and C are lowercase.

Dynamic Programming

if we use dp[i] to represent the shortest distance, obviously, dp[i] = 0 where S[i] == C, otherwise, we have dp[i] = min(dp[i], dp[i – 1] + 1, dp[i + 1] + 1).

The Dynamic Programming approach can then be implemented via two passes, with O(N) complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    vector<int> shortestToChar(string S, char C) {
        int n = S.size();
        vector<int> r(n, n);
        for (int i = 0; i < n; ++ i) {
            if (S[i] == C) r[i] = 0;
        }
        for (int i = 1; i < n; ++ i) {
            r[i] = min(r[i], r[i - 1] + 1);
        }
        for (int i = n - 2; i >= 0; -- i) {
            r[i] = min(r[i], r[i + 1] + 1);
        }
        return r;
    }
};

class Solution {
public:
    vector<int> shortestToChar(string S, char C) {
        int n = S.size();
        vector<int> r(n, n);
        for (int i = 0; i < n; ++ i) {
            if (S[i] == C) r[i] = 0;
        }
        for (int i = 1; i < n; ++ i) {
            r[i] = min(r[i], r[i - 1] + 1);
        }
        for (int i = n - 2; i >= 0; -- i) {
            r[i] = min(r[i], r[i + 1] + 1);
        }
        return r;
    }
};

Two Pointers

For each character in the string, if we know its closet left and right distances to the target character, the answer is the minimal of both. e.g. when iterating index i from left to right, the answer is i – prev, if prev is the last seen position of the target character.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    vector<int> shortestToChar(string S, char C) {
        vector<int> r(S.size(), 0);
        int prev = -S.size();
        for (int i = 0; i < S.size(); ++ i) {
            if (S[i] == C) prev = i;
            r[i] = i - prev;
        }
        prev = INT_MAX;
        for (int i = S.size() - 1; i >= 0; -- i) {
            if (S[i] == C) prev = i;
            r[i] = min(r[i], prev - i);
        }
        return r;
    }
};

class Solution {
public:
    vector<int> shortestToChar(string S, char C) {
        vector<int> r(S.size(), 0);
        int prev = -S.size();
        for (int i = 0; i < S.size(); ++ i) {
            if (S[i] == C) prev = i;
            r[i] = i - prev;
        }
        prev = INT_MAX;
        for (int i = S.size() - 1; i >= 0; -- i) {
            if (S[i] == C) prev = i;
            r[i] = min(r[i], prev - i);
        }
        return r;
    }
};

The above implementation runs at complexity O(N) with two passes.

–EOF (The Ultimate Computing & Technology Blog) —