[LeetCode] 1055. Shortest Way to Form String

[grandyang]

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.

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:

• Both the source and target strings consist of only lowercase English letters from "a"-"z".
• The lengths of source and target string are between 1 and 1000.

这道题说我们可以通过删除某些位置上的字母从而形成一个新的字符串，现在给了两个字符串 source 和 target，问最少需要删除多个字母，可以把 source 字母串拼接成为 target。注意这里的 target 字符串可能会远长于 source，所以需要多个 source 字符串 concatenate 到一起，然后再进行删除字母。对于 target 中的每个字母，都需要在 source 中匹配到，所以最外层循环肯定是遍历 target 中的每个字母，可以使用一个指针j，初始化赋值为0，接下来就要在 source 中匹配这个 target[j]，所以需要遍历一下 source 字符串，如果匹配上了 target[j]，则j自增1，继续匹配下一个，当循环退出后，此时有一种情况需要考虑，就是对于这个 target[j] 字母，整个 source 字符串都无法匹配，说明 target 中存在 source 中没有的字母，这种情况下是要返回 -1 的，如何判定这种情况呢？当然可以在最开始把 source 中所有的字母放到一个 HashSet 中，然后对于 target 中每个字母都检测看是否在集合中。但这里可以使用更简便的方法，就是在遍历 source 之前，用另一个变量 pre 记录当前j的位置，然后当遍历完 source 之后，若j没有变化，则说明有其他字母存在，直接返回 -1 即可，参见代码如下：

解法一：

class Solution {
public:
    int shortestWay(string source, string target) {
        int res = 0, j = 0, m = source.size(), n = target.size();
        while (j < n) {
            int pre = j;
            for (int i = 0; i < m; ++i) {
                if (j < n && source[i] == target[j]) ++j;
            }
            if (j == pre) return -1;
            ++res;
        }
        return res;
    }
};

下面这种方法思路和上面基本一样，就是没有直接去遍历 source 数组，而是使用了 STL 的 find 函数。开始还是要遍历 target 字符串，对于每个字母，首先在 source 中调用 find 函数查找一下，假如找不到，直接返回 -1。有的话，就从 pos+1 位置开始再次查找该字母，且其位置赋值为 pos，注意这里 pos+1 的原因是因为其初始化为了 -1，需要从0开始找，或者 pos 已经赋值为上一个匹配位置了，所以要从下一个位置开始查找。假如 pos 为 -1 了，说明当前剩余字母中无法匹配了，需要新的一轮循环，此时将 res 自增1，并将 pos 赋值为新的 source 串中的第一个匹配位置，参见代码如下：

解法二：

class Solution {
public:
    int shortestWay(string source, string target) {
        int res = 1, pos = -1, n = target.size();
        for (int i = 0; i < n; ++i) {
            if (source.find(target[i]) == -1) return -1;
            pos = source.find(target[i], pos + 1);
            if (pos == -1) {
                ++res;
                pos = source.find(target[i]);
            }
        }
        return res;
    }
};

Github 同步地址:

#1055

类似题目：

Is Subsequence

Number of Matching Subsequences

参考资料：

https://leetcode.com/problems/shortest-way-to-form-string/

https://leetcode.com/problems/shortest-way-to-form-string/discuss/350190/C%2B%2B-solution-faster-than-78.72-of-c%2B%2B-submission

https://leetcode.com/problems/shortest-way-to-form-string/discuss/330938/Accept-is-not-enough-to-get-a-hire.-Interviewee-4-follow-up

LeetCode All in One 题目讲解汇总(持续更新中...)