Advertisement
hoangreal

Shortest way to form strings

Oct 19th, 2024
37
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.51 KB | Source Code | 0 0
  1. """
  2. Count length number of subsequences from 'source' to created 'target'
  3. """
  4. class Solution:
  5.     def solve(self, source: str, target: str) -> int:
  6.         """
  7.        Finds the minimum number of subsequences of 'source' required to form 'target'.
  8.        Returns -1 if 'target' cannot be formed from 'source'.
  9.  
  10.        Time Complexity: O(len(source) * len(target))
  11.        Space Complexity: O(1)
  12.        """
  13.         def match_subsequence(source_idx: int, target_idx: int) -> int:
  14.             # Attempt to match characters in 'target' starting from 'target_idx'
  15.             # by scanning 'source' from 'source_idx'
  16.             while source_idx < source_len and target_idx < target_len:
  17.                 if source[source_idx] == target[target_idx]:
  18.                     target_idx += 1  # Match found, move to next character in 'target'
  19.                 source_idx += 1  # Move to next character in 'source'
  20.             return target_idx  # Return the updated index in 'target'
  21.  
  22.         source_len, target_len = len(source), len(target)
  23.         subsequences_count = 0  # Counts the number of subsequences used
  24.         target_idx = 0  # Current index in 'target'
  25.  
  26.         while target_idx < target_len:
  27.             new_target_idx = match_subsequence(0, target_idx)
  28.             if new_target_idx == target_idx:
  29.                 return -1  # No progress, character not in 'source'
  30.             target_idx = new_target_idx
  31.             subsequences_count += 1  # One subsequence of 'source' used
  32.         return subsequences_count
  33.  
Tags: pinterest
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement