Leetcode 821. Minimum distance of characters (simple) - sequel

Title

821. The shortest distance of a character

understand

Personally, I think yesterday's question is very classic . You can practice a variety of algorithmic ideas on this topic , Lay the foundation for future learning algorithms . Refer to the solutions of other big men , Tidy up 2 A good idea , For your reference .

The central expansion method

Topic ideas

1. Each time you traverse a variable , Defined from this location 2 A pointer to the , To the left , Right traversal . Calculation 2 The minimum value of the distance from the first position to the initial position
2. Record the minimum value in the array

code for Python3

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        #  The central expansion method 
        len_s = len(s) - 1
        arr = []
        for i in range(len(s)):
            shortest = float('inf')
            if s[i] == c:
                arr.append(0)
                continue
            else:
                left, right = i, i
                while left >= 0:
                    if s[left] == c:
                        shortest = min(shortest, i - left)
                        break
                    else:
                        left -= 1
                while right <= len_s:
                    if s[right] == c:
                        shortest = min(shortest, right - i)
                        break
                    else:
                        right += 1
                arr.append(shortest)

        return arr

Copy

Complexity analysis

• Time complexity : O(N²)
• Spatial complexity : O(1) 　　 The extra space complexity used here , Regardless of the space occupied by the returned results !

Sliding window method

Topic ideas

1. With expected string c Is the critical point , Divided into many windows
2. Traverse s Chinese characters , Calculate the distance between the current character and the left and right boundary points of the window , Take the minimum value and put it in the array

code for Python3

class Solution:
  def shortestToChar(self, s: str, c: str) -> List[int]:
      #  Sliding window method 
      arr = []
      left = float('-inf')
      right = s.find(c)
      for i in range(len(s)):
          if i == right:
              #  Update window 
              left = right
              right = s.find(c, right + 1)

          if s[i] == c:
              arr.append(0)
              continue
          else:
          #  Add a judgment ,  If right = -1, That is, when the right boundary of the last window is the string length ,  At this time, the minimum distance is the distance between the current character and the left boundary !
              arr.append(min(i - left, right - i)) if right != -1 else arr.append(i - left)

      return arr

Copy

• Time complexity : O(N) N For the string S The length of
• Spatial complexity : O(1) 　　 The extra space complexity used here , Regardless of the space occupied by the returned results !

python Knowledge about

• Find element in string

# find() Method 
s = "abcdefb"
print(s.find("b"))  # 1
print(s.find("b", 2))  # 6    From the specified position ,  Query the next string 
print(s.find("k"))  # -1

# index Method 
s = "abcdefb"
print(s.index("b")) ## 1
print(s.index("b", 2)) # 6
print(s.index("k"))  # ValueError: substring not found

 so , find  and  index  The usage is basically the same 

 The same thing 
1. Can find the first character in the string 
2. You can specify to start after an index ,  Find the next character to appear 

 Difference 
1.find  When the element cannot be found , Returns the -1
2.index  When the element cannot be found ,  Returns the  ValueError

Copy

• Look for elements in the list

s = ['a', 'b', 'c', 'd', 'e', 'f', 'b']
print(s.index("b"))
print(s.index("b", 2))  # 6


 Be careful  
1.list Search for elements , Only use index,  nothing find Method .

2. When the element cannot be found ,  The same will happen  ValueError It's abnormal 

Copy