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.

Solutions

Solution 1: Two Pointers

We can use the two pointers method, where pointer $j$ points to the target string target. Then we traverse the source string source with pointer $i$ pointing to the source string source. If $source[i] = target[j]$, then both $i$ and $j$ move one step forward, otherwise only pointer $i$ moves. When both pointers $i$ and $j$ reach the end of the string, if no equal character is found, return $-1$, otherwise the subsequence count increases by one, and then set pointer $i$ to $0$ and continue to traverse.

After the traversal ends, return the subsequence count.

The time complexity is $O(m \times n)$, where $m$ and $n$ are the lengths of the strings source and target respectively. The space complexity is $O(1)$.

Python3JavaC++Go

class Solution:
    def shortestWay(self, source: str, target: str) -> int:
        def f(i, j):
            while i < m and j < n:
                if source[i] == target[j]:
                    j += 1
                i += 1
            return j

        m, n = len(source), len(target)
        ans = j = 0
        while j < n:
            k = f(0, j)
            if k == j:
                return -1
            j = k
            ans += 1
        return ans

class Solution {
    public int shortestWay(String source, String target) {
        int m = source.length(), n = target.length();
        int ans = 0, j = 0;
        while (j < n) {
            int i = 0;
            boolean ok = false;
            while (i < m && j < n) {
                if (source.charAt(i) == target.charAt(j)) {
                    ok = true;
                    ++j;
                }
                ++i;
            }
            if (!ok) {
                return -1;
            }
            ++ans;
        }
        return ans;
    }
}

class Solution {
public:
    int shortestWay(string source, string target) {
        int m = source.size(), n = target.size();
        int ans = 0, j = 0;
        while (j < n) {
            int i = 0;
            bool ok = false;
            while (i < m && j < n) {
                if (source[i] == target[j]) {
                    ok = true;
                    ++j;
                }
                ++i;
            }
            if (!ok) {
                return -1;
            }
            ++ans;
        }
        return ans;
    }
};

func shortestWay(source string, target string) int {
    m, n := len(source), len(target)
    ans, j := 0, 0
    for j < n {
        ok := false
        for i := 0; i < m && j < n; i++ {
            if source[i] == target[j] {
                ok = true
                j++
            }
        }
        if !ok {
            return -1
        }
        ans++
    }
    return ans
}

1055. Shortest Way to Form String 🔒

Description

Solutions

Solution 1: Two Pointers

Comments