难度: Medium
Submission
运行时间: 38 ms
内存: 16.1 MB
class Solution:
def shortestWay(self, source: str, target: str) -> int:
dic = [[] for i in range(26)]
for i, ch in enumerate(source):
dic[ord(ch) - ord('a')].append(i)
ans = 1
tmp_idx = -1
for ch in target:
if dic[ord(ch) - ord('a')] == []: return -1
else:
flag = False
for i in dic[ord(ch) - ord('a')]:
if i > tmp_idx:
flag = True
tmp_idx = i
break
if not flag:
ans += 1
tmp_idx = dic[ord(ch) - ord('a')][0]
return ans
Explain
该题解利用了一个贪心算法的思想，主要目标是使用给定的source字符串尽可能多地形成target字符串。首先，创建一个字典dic，里面包含26个空列表，分别对应26个字母的索引。遍历source字符串，将每个字符的索引按字母顺序存储到相应的列表中。对于target中的每个字符，如果在source中找不到该字符，则直接返回-1，表示无法形成。如果找到了，使用二分搜索来寻找可以接上的最小的索引。如果找到了更大的索引，就继续；如果没有找到，表示当前source的遍历已经结束，需要重新开始遍历source，此时计数器ans加1。最后，返回使用source字符串形成target所需的最少次数。
时间复杂度: O(n + m*log(n))
空间复杂度: O(n)
class Solution:
def shortestWay(self, source: str, target: str) -> int:
dic = [[] for i in range(26)] # 创建一个包含26个空列表的字典
for i, ch in enumerate(source): # 遍历source字符串，按字符顺序存储索引
dic[ord(ch) - ord('a')].append(i)
ans = 1 # 初始化计数器，至少需要一次
tmp_idx = -1 # 初始化前一个字符的索引
for ch in target: # 遍历target字符串
if dic[ord(ch) - ord('a')] == []: return -1 # 如果source中没有target的字符，返回-1
else:
flag = False # 标记是否找到了合适的索引
for i in dic[ord(ch) - ord('a')]: # 遍历所有可能的索引
if i > tmp_idx: # 找到了一个合适的索引
flag = True
tmp_idx = i # 更新索引
break
if not flag: # 如果没有找到，表示需要重新开始遍历source
ans += 1 # 计数器加1
tmp_idx = dic[ord(ch) - ord('a')][0] # 从头开始
return ans # 返回最少次数
Explore
选择包含26个空列表的字典（实际上是列表的列表，因为Python中没有严格的字典类型用于此用途）来存储每个字母的索引是因为这样可以快速、直接地访问每个字符的所有出现位置。这种数据结构使得查找和更新操作都非常高效。使用列表的列表而不是哈希表或其他数据结构，是因为字符集限定在26个小写英文字母，可以直接通过字符的ASCII值计算索引，这样做既简单又避免了额外的哈希计算开销，提高了索引和查找的速度。
在遍历target字符串时，使用二分搜索来查找可以接上的最小的索引是因为每个字符对应的索引列表是按照在source中的出现顺序（即升序）排序的。通过二分搜索，我们可以快速找到当前字符在source中的下一个可用位置，这样可以有效地减少查找时间，特别是当source字符串较长时。二分搜索的时间复杂度为O(log n)，比线性搜索O(n)更高效，能够加快整体算法的执行速度。
重新从source的开始位置进行遍历的逻辑是基于贪心算法的思想。每当在当前的source遍历中无法找到target的下一个字符时，意味着必须重新从source的开头开始搜索以继续匹配target。这样做确保了每次都能尽可能多地在当前的source遍历中匹配target中的字符，从而实现在最少的source重复次数中完成target的构建。虽然这种方法不一定保证是绝对的最短路径（在所有可能的source重排中），但在不改变source顺序的前提下，是实现目标的有效且实用的方法。