leetcode-821-Shortest-Distance-to-a-Character

发表于   |  

描述

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:

1
2
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.

分析

题目大意是输出字符串的每个字符到某个字符的最短距离。

最短距离可能是来自左边，也可能来自右边，从左到右遍历一次再从右到左遍历一次即可。

解决方案1(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] shortestToChar(String S, char C) {
        int sizeS = S.length();
        int[] result = new int[sizeS];
        int prev = Integer.MIN_VALUE / 2;
        
        for (int i = 0; i < sizeS; i++) {
            if (S.charAt(i) == C) {
                prev = i;
            }
            result[i] = i - prev;
        }
        
        prev = Integer.MAX_VALUE / 2;
        for (int i = sizeS-1; i >= 0; i--) {
            if (S.charAt(i) == C) {
                prev = i;
            }
            result[i] = Math.min(result[i], prev-i);
        }
        return result;
    }
}

解决方案2（Golang）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func shortestToChar(s string, c byte) []int {
    result := []int{}
    
    for i := range s {
        if s[i] == c {
            result = append(result, 0)
            continue
        }
        nowMin := len(s)
        for j := i+1; j < len(s); j++ {
            if s[j] == c {
                if (j-i) < nowMin {
                    nowMin = j-i
                }
                break
            }
        }
        
        for j := i-1; j >= 0; j-- {
            if s[j] == c {
                if (i-j) < nowMin {
                    nowMin = i - j
                }
                break
            }
        }
        result = append(result, nowMin)
    }
    return result
}

题目来源