Given a string s and a character c that occurs in s, return an array of integers answer where answer.length == s.length and answer[i] is the distance from index i to the closest occurrence of character c in s.
The distance between two indices i and j is abs(i - j), where abs is the absolute value function.
Example 1:
Input: s = "loveleetcode", c = "e" Output: [3,2,1,0,1,0,0,1,2,2,1,0] Explanation: The character 'e' appears at indices 3, 5, 6, and 11 (0-indexed). The closest occurrence of 'e' for index 0 is at index 3, so the distance is abs(0 - 3) = 3. The closest occurrence of 'e' for index 1 is at index 3, so the distance is abs(1 - 3) = 2. For index 4, there is a tie between the 'e' at index 3 and the 'e' at index 5, but the distance is still the same: abs(4 - 3) == abs(4 - 5) = 1. The closest occurrence of 'e' for index 8 is at index 6, so the distance is abs(8 - 6) = 2.
Example 2:
Input: s = "aaab", c = "b" Output: [3,2,1,0]
Constraints:
1 <= s.length <= 104s[i]andcare lowercase English letters.- It is guaranteed that
coccurs at least once ins.
class Solution:
def shortestToChar(self, s: str, c: str) -> List[int]:
n = len(s)
ans = [0] * n
j = inf
for i, ch in enumerate(s):
if ch == c:
j = i
ans[i] = abs(i - j)
j = inf
for i in range(n - 1, -1, -1):
if s[i] == c:
j = i
ans[i] = min(ans[i], abs(i - j))
return ansclass Solution:
def shortestToChar(self, s: str, c: str) -> List[int]:
q = deque([i for i, ch in enumerate(s) if ch == c])
ans = [0 if ch == c else -1 for ch in s]
d = 0
while q:
d += 1
for _ in range(len(q)):
i = q.popleft()
for j in (i - 1, i + 1):
if 0 <= j < len(s) and ans[j] == -1:
ans[j] = d
q.append(j)
return ansclass Solution {
public int[] shortestToChar(String s, char c) {
int n = s.length();
int[] ans = new int[n];
for (int i = 0, j = Integer.MAX_VALUE; i < n; ++i) {
if (s.charAt(i) == c) {
j = i;
}
ans[i] = Math.abs(i - j);
}
for (int i = n - 1, j = Integer.MAX_VALUE; i >= 0; --i) {
if (s.charAt(i) == c) {
j = i;
}
ans[i] = Math.min(ans[i], Math.abs(i - j));
}
return ans;
}
}class Solution {
public int[] shortestToChar(String s, char c) {
Deque<Integer> q = new ArrayDeque<>();
int n = s.length();
int[] ans = new int[n];
Arrays.fill(ans, -1);
for (int i = 0; i < n; ++i) {
if (s.charAt(i) == c) {
q.offer(i);
ans[i] = 0;
}
}
int d = 0;
while (!q.isEmpty()) {
++d;
for (int t = q.size(); t > 0; --t) {
int i = q.poll();
for (int j : Arrays.asList(i - 1, i + 1)) {
if (j >= 0 && j < n && ans[j] == -1) {
ans[j] = d;
q.offer(j);
}
}
}
}
return ans;
}
}function shortestToChar(s: string, c: string): number[] {
const n = s.length;
let ans = [];
let pre = Infinity;
for (let i = 0; i < n; i++) {
if (s.charAt(i) == c) pre = i;
ans[i] = Math.abs(pre - i);
}
pre = Infinity;
for (let i = n - 1; i > -1; i--) {
if (s.charAt(i) == c) pre = i;
ans[i] = Math.min(Math.abs(pre - i), ans[i]);
}
return ans;
}function shortestToChar(s: string, c: string): number[] {
const n = s.length;
const idxs = [];
for (let i = 0; i < n; i++) {
if (s[i] === c) {
idxs.push(i);
}
}
idxs.push(Infinity);
const res = new Array(n);
let i = 0;
for (let j = 0; j < n; j++) {
if (Math.abs(idxs[i] - j) > Math.abs(idxs[i + 1] - j)) {
i++;
}
res[j] = Math.abs(idxs[i] - j);
}
return res;
}impl Solution {
pub fn shortest_to_char(s: String, c: char) -> Vec<i32> {
let c = c as u8;
let s = s.as_bytes();
let n = s.len();
let mut res = vec![i32::MAX; n];
let mut pre = i32::MAX;
for i in 0..n {
if s[i] == c {
pre = i as i32;
}
res[i] = i32::abs(i as i32 - pre);
}
pre = i32::MAX;
for i in (0..n).rev() {
if s[i] == c {
pre = i as i32;
}
res[i] = res[i].min(i32::abs(i as i32 - pre));
}
res
}
}class Solution {
public:
vector<int> shortestToChar(string s, char c) {
int n = s.size();
vector<int> ans(n);
for (int i = 0, j = INT_MAX; i < n; ++i) {
if (s[i] == c) j = i;
ans[i] = abs(i - j);
}
for (int i = n - 1, j = INT_MAX; i >= 0; --i) {
if (s[i] == c) j = i;
ans[i] = min(ans[i], abs(i - j));
}
return ans;
}
};class Solution {
public:
vector<int> shortestToChar(string s, char c) {
int n = s.size();
vector<int> ans(n, -1);
queue<int> q;
for (int i = 0; i < n; ++i)
{
if (s[i] == c)
{
q.push(i);
ans[i] = 0;
}
}
int d = 0;
while (!q.empty())
{
++d;
for (int t = q.size(); t > 0; --t)
{
int i = q.front();
q.pop();
vector<int> dirs{i - 1, i + 1};
for (int& j : dirs)
{
if (j >= 0 && j < n && ans[j] == -1)
{
ans[j] = d;
q.push(j);
}
}
}
}
return ans;
}
};func shortestToChar(s string, c byte) []int {
n := len(s)
ans := make([]int, n)
for i, j := 0, -10000; i < n; i++ {
if s[i] == c {
j = i
}
ans[i] = i - j
}
for i, j := n-1, 10000; i >= 0; i-- {
if s[i] == c {
j = i
}
if j-i < ans[i] {
ans[i] = j - i
}
}
return ans
}func shortestToChar(s string, c byte) []int {
n := len(s)
var q []int
ans := make([]int, n)
for i := range s {
ans[i] = -1
if s[i] == c {
q = append(q, i)
ans[i] = 0
}
}
d := 0
for len(q) > 0 {
d++
for t := len(q); t > 0; t-- {
i := q[0]
q = q[1:]
for _, j := range []int{i - 1, i + 1} {
if j >= 0 && j < n && ans[j] == -1 {
ans[j] = d
q = append(q, j)
}
}
}
}
return ans
}