LC: 1055. Shortest Way to Form String
https://leetcode.com/problems/shortest-way-to-form-string
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 <= 1000sourceandtargetconsist of lowercase English letters.
The Essence:
Das ist ein gutes Problem dafür, die Zwei-Zeiger-Technik anzuwenden. Man soll bemerken, dass die Teilstrings des Zielstrings aus Teilfolgen des Ausgangsstrings bestehen. Die Zeichen dieser zwei Strings müssen also verglichen werden.
Details:
Der Zeiger in dem ersten String wird verschoben, bis die gezeigten Zeichen bei beiden Strings gleich sind. Dann wird der Zeiger bei dem zweiten String zu dem nächsten Zeichen verschoben und es wird in dem ersten String wieder dieses Zeichen gesucht. Wenn der Zeiger in dem ersten String am Ende kommt, dann fängt es vom Anfang wieder an. Die Anzahl der Anfänge ist die gesuchte minimale Anzahl der Teilfolgen.
Solution and Further Explanation:
Default Code:
Last updated