Leetcode solution of Check Array Formation Through Concatenation

Question

I have tested both string based and map based implementations of this problem. The first one gives 12ms runtime while the second one gives 1ms with both using almost same space. And the implementation structure of both styles looks same. So, I want to know why there is a much runtime difference between the two. Here are both the implementations:

class Solution {
    public boolean canFormArray(int[] arr, int[][] pieces) {
        
        // string based
        String str = "";
        for (int i=0; i<arr.length; i++) {
            str = str + arr[i] + "#";
        }
        
        for (int i=0; i<pieces.length; i++) {
            String str2 = "";
            for (int j=0; j<pieces[i].length; j++) {
                str2 = str2 + pieces[i][j] + "#";
            }
            if (!str.contains(str2)) {
                return false;
            }
        }
        
        return true;
        
        // map based
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i=0; i<arr.length; i++) {
            map.put(arr[i], i);
        }
        
        for (int i=0; i<pieces.length; i++) {
            if (!map.containsKey(pieces[i][0])) {
                return false;
            }
            int index = map.get(pieces[i][0]);
            for (int j=1; j<pieces[i].length; j++) {
                if (!map.containsKey(pieces[i][j])) {
                    return false;
                }
                if (map.get(pieces[i][j]) != index+1) {
                    return false;
                }
                index++;
            }
        }
        
        return true;
    }
}

Answer 1

str.contains(str2) has a time complexity of O(nm) in the worst case.

while map.containsKey(pieces[i][0]) has a time complexity of O(1)

Please check this answer as well to find out more details Time complexity of String.contains()