Question

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

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
}