1055 - Shortest Way To Form String
Written on February 2, 2020
Tweet
From any string, we can form a subsequence of that string by deleting some number of characters (possibly no deletions). Given two strings source and target, return the minimum number of subsequences of source such that their concatenation equals target. If the task is impossible, return -1.
class Solution:
def shortestWay(self, source: str, target: str) -> int:
ret = j = 0
while j < len(target):
i = 0
found = False
while i < len(source) and j < len(target):
if source[i] == target[j]:
j += 1
found = True
i += 1
if found:
ret += 1
else:
return -1
return ret