设计 / 思考 / 材料 / 信息

0%

LeetCode | Shortest Distance to a Character (easy level)

发表于 更新于 Valine：

Problem 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.

Good solution for simplicity

1
2
3
4
5
6
7
8
9
class Solution:
    def shortestToChar(self, S, C):
        """
        :type S: str
        :type C: str
        :rtype: List[int]
        """
        clist=[i for i,v in enumerate(S) if v==C]
        return [min(abs(i-x) for i in clist) for x in range(len(S))]

This demo uses a generator to generate 2 lists:

one list (clist) stores position where letter equals to C, the other helps to output the final return list, which calculate every distances between letters and clist elements.

However, most of the distances calculation are not necessary. Thus, this method is simple to write, but not the fatest.

Good solution for efficiency

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
class Solution:
    def shortestToChar(self, S, C):
        """
        :type S: str
        :type C: str
        :rtype: List[int]
        """
        stack = []
        last_C = None
        output = [0] * len(S)
        for idx, ch in enumerate(S):
            if ch != C:
            	stack.append(idx)
            else:
                while stack:
                    last_idx = stack.pop()
                    if last_C is None:
                    	output[last_idx] = idx - last_idx
                    else:
                    	output[last_idx] = min(
                            idx - last_idx,
                            last_idx - last_C)
                last_C = idx
        while stack:
            last_idx = stack.pop()
            output[last_idx] = last_idx - last_C if last_idx is not None else -1
        return output

This method uses a stack data structure. stack append and stack pop.

For each screened letter, it compares two distances.

My ugly solution — faster than 71.17%

My solution avoid most of the meaningless calculation in the most simple one, so it’s a litter bit faster.

The main point of my solution is to generate an interval defined by left and right. We have to screen string list used enumerate from left to right. index points to where we are, if we are in the interval, we have to compare distance to left and right; if not, we have to redefined left and right, then compare.

So for every letter, there are only two distances waiting to be calculated and compared. 

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
class Solution:
    def shortestToChar(self, S, C):
        """
        :type S: str
        :type C: str
        :rtype: List[int]
        """
        listEqC = []
        for index, obj in enumerate(S):
            if obj == C:
                listEqC.append(index)
        return_list = []
        pointer = 0
        if listEqC != []:
            left = right = listEqC[pointer]
        else:
            left = right = float('inf')
        for index, obj in enumerate(S):
            if index >= right and pointer != len(listEqC)-1:
                pointer += 1
                left = right
                right = listEqC[pointer]
            left_distance = abs(index-left)
            right_distance = abs(index-right)
            return_list.append(min(left_distance, right_distance))
        return return_list