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.

• Java
• C++
• Python
• Go
• TypeScript
• RenderScript

• 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