Leetcode 821. 字符的最短距离(简单) - 续集

题目名称

821. 字符的最短距离

理解

个人觉得昨天的这个题很经典.大家可以此题为基础练习多种算法思想, 为以后学习算法打基础.参考其它大佬的解法, 整理了2个不错的思路, 方便大家参考.

中心扩展法

题目思路

1. 每次遍历到一个变量时, 从该位置定义2个指针, 分别向左, 右遍历.计算2个位置到初始位置距离的最小值
2. 将该最小值记录到数组中

code for Python3

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        # 中心扩展法
        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

复制

复杂度分析

• 时间复杂度: O(N²)
• 空间复杂度: O(1) 　　此处使用的是额外空间复杂度, 不考虑返回结果占用的空间!

滑动窗口法

题目思路

1. 以预期字符串c为临界点, 划分为很多个窗口
2. 遍历s中字符时, 分别计算当前字符与所在窗口左右边界点的距离,取最小值放到数组中

code for Python3

class Solution:
  def shortestToChar(self, s: str, c: str) -> List[int]:
      # 滑动窗口法
      arr = []
      left = float('-inf')
      right = s.find(c)
      for i in range(len(s)):
          if i == right:
              # 更新窗口
              left = right
              right = s.find(c, right + 1)

          if s[i] == c:
              arr.append(0)
              continue
          else:
          # 加了个判断, 如果right = -1,即最后一个窗口的右边界为字符串长度时, 此时的最小距离为当前字符与左边界的距离!
              arr.append(min(i - left, right - i)) if right != -1 else arr.append(i - left)

      return arr

复制

• 时间复杂度: O(N) N为字符串S的长度
• 空间复杂度: O(1) 　　此处使用的是额外空间复杂度, 不考虑返回结果占用的空间!

python的相关知识

• 字符串中查找元素

# find()方法
s = "abcdefb"
print(s.find("b"))  # 1
print(s.find("b", 2))  # 6   从指定位置后, 查询下一个字符串
print(s.find("k"))  # -1

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

可见, find 和 index 使用方法基本相同

相同点
1.都可以查找字符串中第一个出现的字符
2.都可以指定从某一个索引后面开始, 查找下一个出现的字符

不同点
1.find 找不到元素时,会返回-1
2.index 找不到元素时, 会返回 ValueError

复制

• 列表中查找元素

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


注意 
1.list中查找元素,只能使用index, 无find方法.

2.查找不到元素时, 一样会出现 ValueError的异常

复制