821. Shortest Distance to a Character --------E ！！！！！！！！！

Q:

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 1:

Input: S = "loveleetcode", C = 'e'
Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

 

Note:

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

A:

利用了普通的BSF。去搜索。

class Solution {
public:
    vector<int> shortestToChar(string S, char C) {
        int n = S.length();
        vector<int> res(n,-1);
        vector<int> curLayer ;
        for(int i =0;i<n;++i)
            if(S[i] == C){
                res[i] = 0;
                curLayer.push_back(i);
            }
        int curDist = 0;
        while(!curLayer.empty()){
            vector<int> newLayer;
            curDist++;
            for(auto i : curLayer){
                if(i-1>= 0 && res[i-1] < 0){
                    newLayer.push_back(i-1);
                    res[i-1] = curDist;
                }
                    
                if(i+1 <n && res[i+1] < 0){
                    newLayer.push_back(i+1);
                    res[i+1] = curDist;
                }
            }
            curLayer = newLayer;
        }
        return res;
    }
};

错误在于，和Facebook面试的时候一样。应该先更改值。再加入临近的index

***********Method 2****************

从左右两边分别找。 然后assign distance

class Solution {
public:
    vector<int> shortestToChar(string S, char C) {
        int n = S.length();
        vector<int> res(n,n);
        int minDist = n;
        // from left to right
        for(int i =0;i<n;i++)
        {
            if(S[i]==C){
                minDist = 0;
            }
            res[i] = min(res[i], minDist);
            minDist++;
        }
        // from right to left
        for(int i =n-1; i>=0; --i)
        {
            if(S[i]==C){
                minDist = 0;
            }
            res[i] = min(res[i], minDist);
            minDist++;
        }
        return res;
    }
};