Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/821.html

821. Shortest Distance to a Character (Easy)

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.

Companies:
Bloomberg

Solution 1.

  • class Solution {
        public int[] shortestToChar(String S, char C) {
            int length = S.length();
            int[] distances = new int[length];
            List<Integer> indices = new ArrayList<Integer>();
            for (int i = 0; i < length; i++) {
                if (S.charAt(i) == C)
                    indices.add(i);
            }
            int size = indices.size();
            int pointer = 0;
            for (int i = 0; i < length; i++) {
                if (indices.contains(i)) {
                    distances[i] = 0;
                    pointer++;
                } else {
                    if (pointer == 0) {
                        int curIndex = indices.get(pointer);
                        distances[i] = Math.abs(curIndex - i);
                    } else if (pointer == size) {
                        int prevIndex = indices.get(pointer - 1);
                        distances[i] = Math.abs(i - prevIndex);
                    } else {
                        int prevIndex = indices.get(pointer - 1), curIndex = indices.get(pointer);
                        distances[i] = Math.min(Math.abs(i - prevIndex), Math.abs(curIndex - i));
                    }
                }
            }
            return distances;
        }
    }
    
    ############
    
    class 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;
        }
    }
    
  • // OJ: https://leetcode.com/problems/shortest-distance-to-a-character/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        vector<int> shortestToChar(string s, char c) {
            int N = s.size(), prev = -N, next = 0;
            vector<int> ans(N);
            for (int i = 0; i < N; ++i) {
                while (next < N && s[next] != c) ++next; 
                if (next == N) next = N + N;
                ans[i] = min(i - prev, next - i);
                if (s[i] == c) prev = i, next++;
            }
            return ans;
        }
    };
    
  • 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 ans
    
    ############
    
    class Solution:
        def shortestToChar(self, S, C):
            """
            :type S: str
            :type C: str
            :rtype: List[int]
            """
            _len = len(S)
            index = -1000000
            ans = [0] * _len
            for i, s in enumerate(S):
                if s == C:
                    index = i
                ans[i] = abs(i - index)
            index = -100000
            for i in range(_len - 1, -1 , -1):
                if S[i] == C:
                    index = i
                ans[i] = min(abs(i - index), ans[i])
            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
    }
    
  • 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;
    }
    
    
  • 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
        }
    }
    
    

All Problems

All Solutions