Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- """
- Count length number of subsequences from 'source' to created 'target'
- """
- class Solution:
- def solve(self, source: str, target: str) -> int:
- """
- Finds the minimum number of subsequences of 'source' required to form 'target'.
- Returns -1 if 'target' cannot be formed from 'source'.
- Time Complexity: O(len(source) * len(target))
- Space Complexity: O(1)
- """
- def match_subsequence(source_idx: int, target_idx: int) -> int:
- # Attempt to match characters in 'target' starting from 'target_idx'
- # by scanning 'source' from 'source_idx'
- while source_idx < source_len and target_idx < target_len:
- if source[source_idx] == target[target_idx]:
- target_idx += 1 # Match found, move to next character in 'target'
- source_idx += 1 # Move to next character in 'source'
- return target_idx # Return the updated index in 'target'
- source_len, target_len = len(source), len(target)
- subsequences_count = 0 # Counts the number of subsequences used
- target_idx = 0 # Current index in 'target'
- while target_idx < target_len:
- new_target_idx = match_subsequence(0, target_idx)
- if new_target_idx == target_idx:
- return -1 # No progress, character not in 'source'
- target_idx = new_target_idx
- subsequences_count += 1 # One subsequence of 'source' used
- return subsequences_count
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement