https://leetcode.com/problems/check-array-formation-through-concatenation

Solution 1, using strings

Imagine, that we have array [3, 4, 18, 6, 8] and pieces [4, 18], [6, 8], [3]. Let us create strings from original string and from parts in the following way: !3!4!18!6!8! for arr and !4!18!, !6!8! and !3! for pieces. Then what we need to check is just if all of our pieces are substrings of first string. We can state this, because all numbers are different.

Complexity: time complexity is O(n^2) to check all substrings and space is O(n).

class Solution:
    def canFormArray(self, arr, pieces):
        arr_str = "!".join(map(str, arr)) + "!"
        return all("!".join(map(str, p)) + "!" in arr_str for p in pieces)

Solution 2, using hash table.

Let us create correspondences d between each start of piece and the whole piece. Then we iterate over our arr and for each number check if we have piece starting with this number: if we have, we add it to constructed list, if not, add nothing. In this way, each what is constucted in the end equal to arr if and only if answer for our problem is True. Why though? Imagine [1, 2, 3, 4, 5] and pieces [1, 2] and [3, 4, 5]. Then we go element by element and have [1, 2] + [] + [3, 4, 5] + []. Imagine now, that we have pieces [1, 2] and [4, 5]. Then what will be reconstructed is [1, 2] + [] + [] + [4, 5] + [].

Complexity: time and space complexity is O(n).

class Solution:
    def canFormArray(self, arr, pieces):
        d = {x[0]: x for x in pieces}
        return list(chain(*[d.get(num, []) for num in arr])) == arr

If you like the solution, you can upvote it on leetcode discussion section: Problem 1640