Determine if two strings are match

Two texts are considered to "match" if they have a common substring of at least length n. Describe an algorithm to determine if two strings are matches.

This is another FB interview question. The reason I am writing this blog is that lots of people are talking about using DP, i.e., find the longest common substring. However, I find it unnecessary and more expensive. I implemented both methods and did some performance test.

//hashset method
 public static boolean isMatch(String s1, String s2, int n) {
  if (s1 == null || s2 == null || s1.length() < n || s2.length() < n)
   return false;
  Set substrings = new HashSet ();
  for (int i = 0; i <= s1.length() - n; i++) {
   substrings.add(s1.substring(i, i + n));
  }
  for (int i = 0; i <= s2.length() - n; i++) {
   if(substrings.contains(s2.substring(i, i + n)))
    return true;
  }
  return false;
 }
 //DP method
 public static boolean isMatch2(String s1, String s2, int n) {
  if (s1 == null || s2 == null || s1.length() < n || s2.length() < n)
   return false;
  int lcs = longestCommonSubstring(s1, s2);
  return lcs >= n;
 }
 public static int longestCommonSubstring(String s1, String s2) {
  if (s1 == null || s2 == null)
   throw new NullPointerException("Null string(s)!");
  int[][] lcs = new int[s1.length() + 1][s2.length() + 1];
  int max = 0;
  for (int i = 1; i <= s1.length(); i++) {
   for (int j = 1; j <= s2.length(); j++) {
    if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
     lcs[i][j] = lcs[i - 1][j - 1] + 1;
    }
    max = Math.max(lcs[i][j], max);
   }
  }
  return max;
 }

The hashset method takes O(m + n) time but DP takes O(mn) time. And the memory usage is almost same.