Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1055.html

1055. Shortest Way to Form String

Level

Medium

Description

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.

Solution

Use two pointers in source and target respectively. Both pointers are initialized to 0.

Each time starting from the pointer of target, find the longest subsequence of source in target. A subsequence in target ends when either the pointer in source reaches the end or the pointer in target reaches the end. If a longest subsequence has length 0, then the character in target does not exist in source, so return -1. Otherwise, increase the number of subsequences by 1, and find the next subsequence in target starting from the updated pointer in target. Finally, return the number of subsequences.

• Java
• Python
• C++
• Go

• class Solution {
      public int shortestWay(String source, String target) {
          int count = 0;
          int targetLength = target.length();
          int startIndex = 0;
          while (startIndex < targetLength) {
              startIndex = longestSubsequence(source, target, startIndex);
              if (startIndex < 0)
                  return -1;
              else
                  count++;
          }
          return count;
      }
  
      public int longestSubsequence(String source, String target, int startIndex) {
          int sourceLength = source.length(), targetLength = target.length();
          int sourceIndex = 0, targetIndex = startIndex;
          while (sourceIndex < sourceLength && targetIndex < targetLength) {
              char c1 = source.charAt(sourceIndex), c2 = target.charAt(targetIndex);
              if (c1 == c2)
                  targetIndex++;
              sourceIndex++;
          }
          if (targetIndex == startIndex)
              return -1;
          else
              return targetIndex;
      }
  }
  

• 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.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
  }
  

All Problems

All Solutions