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:
S
string length is in[1, 10000].
C
is a single character, and guaranteed to be in stringS
.- All letters in
S
andC
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; } };
No comments:
Post a Comment