Funcia
Lv.2dpstring

Merging Two Trains

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Two freight trains merge onto one track. Each car carries a one-letter cargo code; reading the first train from the front gives s1, the second gives s2.

While merging, the front-most remaining car of either train is detached and appended to the new train, again and again, until every car of both trains has been used exactly once. So the cars of each train keep their relative order.

Given s3, the codes of the merged train from the front, return true if s3 can be produced from s1 and s2 this way, otherwise false.

Examples

s1s2s3result
"aabcc""dbbca""aadbbcbcac"true
"aabcc""dbbca""aadbbbaccc"false
"ab""cd""abcde"false

Example 1 — Take "aa" from s1, "dbbc" from s2, "bc" from s1, "a" from s2, then "c" from s1.

Example 2 — No order of taking cars produces s3.

Example 3 — The lengths do not match; s3 must use exactly all cars of both trains.

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(s1: string, s2: string, s3: string) → bool

Constraints

  • 1≤1 \le s1.length ≤1,500\le 1{,}500
  • 1≤1 \le s2.length ≤1,500\le 1{,}500
  • 1≤1 \le s3.length ≤3,000\le 3{,}000
  • All three strings consist of lowercase English letters only.

Expected complexity

Time
O(NM)
Space
O(M)

Examples

s1s2s3Expected
"aabcc""dbbca""aadbbcbcac"true
"aabcc""dbbca""aadbbbaccc"false
"ab""cd""abcde"false

Hint

Hint

If the lengths do not add up, answer false. After taking i cars from s1 and j from s2 the merged train must equal the first i + j letters of s3, so (i, j) is the whole state: ok[i][j] = (ok[i-1][j] and s1[i-1] == s3[i+j-1]) or (ok[i][j-1] and s2[j-1] == s3[i+j-1]). Branching recursion explodes on inputs like "aaa…a"; filling the table is O(NM)O(NM).

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4014verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.