mediumStringsPattern: Pointer Linkage
Interleaved String Reconstruction Solution
Problem Statement
Given two strings s1 and s2 and a third string result, determine if result is an interleaving of s1 and s2, such that the characters in the first string and second string are used exactly once in the interleaved string and they can appear in any order, but the characters of each string must be in their original order in the interleaved string.
Examples
Example 1:
Input:s1 = "abc", s2 = "pqr", result = "apbqcr"
Output:true
Explanation: The string "apbqcr" is an interleaving of "abc" and "pqr" because 'a' appears before 'b', 'b' appears before 'c', 'p' appears before 'q', and 'q' appears before 'r' in "apbqcr".
Example 2:
Input:s1 = "abc", s2 = "pqr", result = "apqcbr"
Output:false
Explanation: The string "apqcbr" is not an interleaving of "abc" and "pqr" because in the result string, 'q' appears before 'b', but 'b' should appear after 'a' and before 'c' from "abc", and 'q' and 'r' should maintain their order from "pqr".
Constraints
- 1 ≤ length(s1), length(s2) ≤ 100
- length(s1) + length(s2) = length(result)
- All characters in the strings are lowercase English letters
Time: O(n*m) Space: O(n*m)
A more efficient approach is to use dynamic programming to build a 2D table where each cell represents whether the substrings up to that point are an interleaving. This approach has a time complexity of O(n*m), where n and m are the lengths of the two input strings.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.