＃ Leetcode 821. Minimum distance of characters (simple)

Title

821. The shortest distance of a character

Think of your own solution

Topic ideas

• Traversal string ｓ, Get expected character of record ｃ stay ｓ List of all locations in list_c
• Define a method : Get the input character and All the elements in the list The lowest absolute value of all the differences
• Traversal string s, Every time you traverse to a character , Call the custom method once , Record to array

code for Python3

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        list_c = [i for i in range(len(s)) if s[i] == c]
        arr = []
        for j in range(len(s)):
            arr.append(self.get_abs_minnum(j, list_c))
        return arr

    def get_abs_minnum(self, first_num:int, li:List):
        cur = pow(10, 4)
        for v in li:
            cur = min(cur, abs(v - first_num))
        return cur

Copy

Complexity analysis

• Time complexity : O(N²) 　　 reason : Double loop , Every time I traverse the string s when , It's all traversed once list_c
• Spatial complexity : O(N) 　　 reason : list_c The size of the space occupied and the string s The length of

Official explanation

I have studied the official solution carefully , I found that the idea was particularly ingenious , Its ideas are worth learning !

Topic ideas

• First traverse from left to right S, Record the current character and C Absolute value of distance . Before the expected value , This position is replaced by positive infinity ; After the expected value appears , Record the actual distance
• Traverse once from right to left S, alike Record the current character and C Absolute value of distance .
• In the 2 During the second traversal , Take the absolute value of the current traversal result And The first 1 Secondary traversal value The minimum value of , Add to array

code for Python3

class Solution(object):
    def shortestToChar(self, S, C):
        prev = float('-inf')
        arr = []
        for i, x in enumerate(S):
            if S[i] == C:
                prev = i
            else:
                arr.append(i - prev)
                
        prev = float('inf')
        for i in range(len(S) -1, -1, -1):
            if S[i] == C:
                prev = i
            else:
                arr.append(min(prev-i, arr[i]))
        return arr

Copy

Complexity analysis

• Time complexity : O(N) 　　 reason : Only traversed 2 Substring S
• Spatial complexity : O(N) 　　 reason : arr Length of array

python Knowledge about

• enumerate Method : In the output data structure Indexes and value When you use

s = "abcdefg"
for i, j in enumerate(s):
    print(i, j)

 The result is :
0 a
1 b
2 c
3 d
4 e
5 f
6 g

--------------------------------------------------

for k in enumerate(s):
    print(k)

 The result is :
(0, 'a')
(1, 'b')
(2, 'c')
(3, 'd')
(4, 'e')
(5, 'f')
(6, 'g')

Copy

• About python Infinity in , An infinitesimal

 Define infinity : float('inf')
 Define infinitesimal : float('-inf')

 A special case :
0* infinity  or 0* An infinitesimal     The result is nan( It's not a number ,  All and nan Can't get the result )

 Other examples :
float('nan') + 9999999   # nan
float('nan') - 9999999   # nan
float('nan') * 9999999   # nan

0 -  An infinitesimal  ->  infinity 
0 - float('-inf')   # float('inf')

Copy

• The reverse order output of the list

s = [1,2,3,4,5]
for i in range(len(s) - 1, -1, -1):
  print(s[i])

 The result is :
5
4
3
2
1

Copy