leetcode - 1055. Shortest Way to Form String
Description
A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., “ace” is a subsequence of “abcde” while “aec” is not).
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.
Example 1:
Input: source = "abc", target = "abcbc"
Output: 2
Explanation: The target "abcbc" can be formed by "abc" and "bc", which are subsequences of source "abc".
Example 2:
Input: source = "abc", target = "acdbc"
Output: -1
Explanation: The target string cannot be constructed from the subsequences of source string due to the character "d" in target string.
Example 3:
Input: source = "xyz", target = "xzyxz"
Output: 3
Explanation: The target string can be constructed as follows "xz" + "y" + "xz".
Constraints:
1 <= source.length, target.length <= 1000
source and target consist of lowercase English letters.
Solution
DP (TLE)
Use dp[i] to denote the minimum number of subsequence we need to form target[:i], then the transformation equation is:
d
p
[
i
]
=
min
(
d
p
[
k
−
1
]
)
+
1
,
∀
k
that
t
a
r
g
e
t
[
k
:
i
]
is a subsequence of source
dp[i] = \min(dp[k - 1]) + 1, \forall k \; \text{that }target[k:i] \text{ is a subsequence of source}
dp[i]=min(dp[k−1])+1,∀kthat target[k:i] is a subsequence of source
Time complexity:
o
(
t
a
r
g
e
t
.
l
e
n
2
∗
s
o
u
r
c
e
.
l
e
n
)
=
o
(
n
3
)
o(target.len^2*source.len)=o(n^3)
o(target.len2∗source.len)=o(n3)
Space complexity:
o
(
t
a
r
g
e
t
.
l
e
n
)
o(target.len)
o(target.len)
Greedy
Go through target, and if the current character is not the same as source, move the pointer in source one step forward. Start over when it’s the end of source.
Time complexity:
o
(
t
a
r
g
e
t
.
l
e
n
∗
s
o
u
r
c
e
.
l
e
n
)
o(target.len*source.len)
o(target.len∗source.len)
Space complexity:
o
(
1
)
o(1)
o(1)
Code
DP (TLE)
class Solution:
def shortestWay(self, source: str, target: str) -> int:
def is_subsequence(source: str, target: str) -> bool:
i, j = 0, 0
while i < len(source) and j < len(target):
if source[i] == target[j]:
i += 1
j += 1
else:
i += 1
return j >= len(target)
if set(target) - set(source):
return -1
dp = [i + 1 for i in range(len(target))]
for i in range(1, len(target)):
for k in range(i + 1):
if is_subsequence(source, target[k: i + 1]):
dp[i] = min(dp[i], 1 + (dp[k - 1] if k - 1 >= 0 else 0))
return dp[-1]
Greedy
class Solution:
def shortestWay(self, source: str, target: str) -> int:
if set(target) - set(source):
return -1
source_index, target_index = 0, 0
res = 0
while target_index < len(target):
if target[target_index] == source[source_index]:
target_index += 1
source_index += 1
if source_index == len(source):
source_index = 0
res += 1
return res + (1 if source_index != 0 else 0)
原文地址：https://blog.csdn.net/sinat_41679123/article/details/145206324
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！