[Python] 2 Solutions, explained
Solution 1, using strings\n\nImagine, 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 p
### Solution 1, using strings\n\nImagine, 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.\n\n**Complexity**: time complexity is `O(n^2)` to check all substrings and space is `O(n)`.\n\n```\nclass Solution:\n    def canFormArray(self, arr, pieces):\n        arr_str = "!".join(map(str, arr)) + "!"\n        return all("!".join(map(str, p)) + "!" in arr_str for p in pieces)\n```\n\n### Solution 2, using hash table.\n\n 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] + []`.\n \n **Complexity**: time and space complexity is `O(n)`.\n\n```\nclass Solution:\n    def canFormArray(self, arr, pieces):\n        d = {x[0]: x for x in pieces}\n        return list(chain(*[d.get(num, []) for num in arr])) == arr\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
[]