原题地址

2901.png

方法一 双指针

我们可以通过双指针算法来判断一个串是否能由s串删除某些元素得到。

拿第一个例子来说明： s="abpcplea", d[0]="ale"

  1. 定义双指针p,q，分别指向s,d[0]，计数器count
  2. 开始遍历：
    • 如果匹配成功，比如s[0] == d[0][0]，则p++,q++,count++
    • 如果匹配不成功，则p++
  3. 如果最后count==len(d[0])，说明全部匹配成功。

子串匹配代码

  1. def inStr(i):
  2.     p = q = count = 0  # 双指针，计数器
  3.     slen, dlen = len(s), len(d[i]) # s串和子串的长度
  4.     while p < slen and q < dlen:
  5.         if s[p] == d[i][q]:  # 匹配成功一个字符
  6.             count += 1
  7.             q += 1
  8.         p += 1  
  9.     if count == dlen:
  10.         return True
  11.     return False

有了上面的代码，问题就很简单了，每次调用inStr()函数来判断是否为s的”子串”，再更新当前记录的结果。

Python代码

  1. def findLongestWord(self, s: str, d: List[str]) -> str:
  2.     def inStr(i):   # 判断子串函数
  3.         p = q = count = 0
  4.         slen, dlen = len(s), len(d[i])
  5.         while p < slen and q < dlen:
  6.             if s[p] == d[i][q]:
  7.                 count += 1
  8.                 q += 1
  9.             p += 1
  10.         if count == dlen:
  11.             return True
  12.         return False
  14.     rel = ''
  15.     for i in range(len(d)):
  16.         if inStr(i) and len(d[i]) >= len(rel):
  17.             # 如果该串更长  或者  长度和rel一样但是字典序更靠前，    则更新
  18.             if len(d[i]) > len(rel) or (len(d[i]) == len(rel) and d[i] < rel):
  19.                 rel = d[i]
  21.     return rel

时间复杂度O(mn)

两层循环，外层长度为len(d)，记为m，内层长度最长为max(len(s),len(d[i]))，记为n，m<n，所以时间复杂度为O(mn)

空间复杂度O(x)

这里的s表示结果串rel的长度