LeetCode 1640. Can I connect to form an array

1640. Can you join to form an array

Give you an array of integers arr , Every integer in the array Different from each other . There's another array of integers pieces, The integers are also Different from each other . Please use In any order Connect pieces In order to form arr . however , Don't allow For each array pieces[i] Reorder integers in .

If you can connect pieces The array in the form of arr , return true ; otherwise , return false .

Example 1：

 Input ：arr = [85], pieces = [[85]]
 Output ：true

Example 2：

 Input ：arr = [15,88], pieces = [[88],[15]]
 Output ：true
 explain ： Connect in turn  [15]  and  [88]

Example 3：

 Input ：arr = [49,18,16], pieces = [[16,18,49]]
 Output ：false
 explain ： Even if the numbers match , You can't rearrange  pieces[0]

Example 4：

 Input ：arr = [91,4,64,78], pieces = [[78],[4,64],[91]]
 Output ：true
 explain ： Connect in turn  [91]、[4,64]  and  [78]

Example 5：

 Input ：arr = [1,3,5,7], pieces = [[2,4,6,8]]
 Output ：false

Tips ：

• 1 <= pieces.length <= arr.length <= 100
• sum(pieces[i].length) == arr.length
• 1 <= pieces[i].length <= arr.length
• 1 <= arr[i], pieces[i][j] <= 100
• arr The integer Different from each other
• pieces The integer Different from each other （ in other words , If you will pieces Flatten it into a one-dimensional array , All integers in an array are different from each other ）

Two 、 Method 1

Hash

class Solution {
    
    public boolean canFormArray(int[] arr, int[][] pieces) {
    
        Map<Integer, int[]> map = new HashMap<>();
        for (int[] piece : pieces) {
    
            map.put(piece[0], piece);
        }
        for (int i = 0; i < arr.length;) {
    
            int cur = arr[i];
            if (map.containsKey(cur)) {
    
                int[] pos = map.get(cur);
                for (int x : pos) {
    
                    if (arr[i] == x) {
    
                        i++;
                    } else {
    
                        return false;
                    }
                }
            } else {
    
                return false;
            }
        }
        return true;
    }
}

Complexity analysis

• Time complexity ：O(n).

• Spatial complexity ：O(n).