Form Array by Concatenating Subarrays of Another Array LeetCode solution in C++

1
class Solution {
2
 public:
3
  // Idea is to use KMP Longest Prefix Suffix array to match if one array is
4
  // subarray of another array.
5
  bool canChoose(vector<vector<int>> &groups, vector<int> &nums) {
6
    int m = nums.size();
7
    int index = 0;
8
    for (auto group : groups) {
9
      int n = group.size();
10
      // Step-1 Generate LPS
11
      vector<int> lps(n, 0);
12
      for (int i = 1; i < n; i++) {
13
        int j = lps[i - 1];
14
        while (j > 0 && group[i] != group[j]) {
15
          j = lps[j - 1];
16
        }
17
        if (group[i] == group[j]) {
18
          j++;
19
        }
20
        lps[i] = j;
21
      }
22

23
      // Step 2 - Matching
24
      int j = 0;
25
      while (index < m) {
26
        if (nums[index] == group[j]) {
27
          j++;
28
          index++;
29
        }
30
        if (j == n)
31
          break;
32
        else if (index < m && nums[index] != group[j]) {
33
          if (j > 0) {
34
            j = lps[j - 1];
35
          } else {
36
            index++;
37
          }
38
        }
39
      }
40
      if (j != n) return false;
41
    }
42

43
    return true;
44
  }
45
};