Search for a sequence in a 2D array - EPI

Search for a sequence in a 2D array StringInMatrix.java

  public static boolean match(int[][] A, List<Integer> S) {
    Set<Tuple<Integer, Integer, Integer>> cache = new HashSet<>();
    for (int i = 0; i < A.length; ++i) {
      for (int j = 0; j < A[i].length; ++j) {
        if (matchHelper(A, S, cache, i, j, 0)) {
          return true;
        }
      }
    }
    return false;
  }

  private static boolean  matchHelper(int[][] A, List<Integer> S,
              Set<Tuple<Integer, Integer, Integer>> cache,
              int i, int j, int len) {
    if (S.size() == len) {
      return true;
    }

    if (i < 0 || i >= A.length || j < 0 || j >= A[i].length
        || cache.contains(new Tuple<>(i, j, len))) {
      return false;
    }

    if (A[i][j] == S.get(len)
        && (matchHelper(A, S, cache, i - 1, j, len + 1)
        || matchHelper(A, S, cache, i + 1, j, len + 1)
        || matchHelper(A, S, cache, i, j - 1, len + 1) || matchHelper(A, S,
        cache, i, j + 1, len + 1))) {
      return true;
    }
    cache.add(new Tuple<>(i, j, len));
    return false;
  }