Google – Multiple Strings Pattern Matching

Google – Multiple Strings Pattern Matching
输入一个pattern，和一堆strings，做跨string的pattern matching.
比如:
patter: "abc"
strs: "ab", "cd" => true
strs: "aa", "bcd" => true
strs: "ab", "ac" => false
strings的输入是一个iterator，只能往前，不能往后。

[Solution]
Greedy
KMP
两种方法各有利弊，greedy edge cases很多。kmp虽然简单，但是把所有strings串起来内存很可能不够。
[Solution #1] – Greedy
Greedy的解法要记住前面是否有已经匹配的，随时要判断是继续匹配前面的，还是重新开始匹配当前的。
[Solution #2] – KMP
把iterator里的所有string串起来，对pattern做kmp
Cons: 注意内存不够的情况。
[Solution #3] – KMP with Cut
但是内存不够的情况也还是有解决办法。分段处理。（前提是pattern必须得放的进内存）
比如内存只能放m个字符（这里排除了pattern所占的空间，假设除去pattern之后，还能塞m个），串起来之后的总长度为n，那么每次取m个字符和pattern来匹配，

1. 如果匹配成功，返回true。
2. 如果完全没有匹配，把下一段m长度丢进来。
3. 如果匹配了k个字符，这k个字符必须是m个字符的suffix，那么就丢掉前面(m – k)个字符，加入下一段(m – k)，从pattern的k + 1位置开始继续往下匹配。
4. 如果在第3种情况下，后面加入的(m – k)个字符又都被匹配成功了，那么我们可以把目前内存里所有m个字符全部丢掉，加入下一段，从pattern的m + 1位置继续往下匹配。（不需要假设pattern长度小于m）

这样时间复杂度依然是O(LEN), where LEN is the sum of length of all strings in the iterator.

class Solution {

  public boolean patternMatch(String pattern, Iterator<String> it) {

    if (pattern == null || pattern.isEmpty() || it == null) {

      return false;

    }

 

    int prevStart = 0;

    while (it.hasNext()) {

      String curr = it.next();

      int currStart = 0;

 

      for (int i = 0; i < curr.length(); i++) {

        char c = curr.charAt(i);

        if (prevStart != -1 && currStart != -1 && pattern.charAt(prevStart) == c && pattern.charAt(currStart) == c) {

          prevStart++;

          currStart++;

        }

        else if (prevStart != -1 && pattern.charAt(prevStart) == c) {

          prevStart++;

          if (c == pattern.charAt(0)) {

            currStart = 1;

          }

          else {

            currStart = -1;

          }

        }

        else if (currStart != -1 && pattern.charAt(currStart) == c) {

          currStart++;

          prevStart = -1;

        }

        else {

          if (c == pattern.charAt(0)) {

            currStart = 1;

          }

          else {

            currStart = -1;

          }

          prevStart = -1;

        }

 

        if (prevStart == pattern.length() || currStart == pattern.length()) {

          return true;

        }

 

      }

 

      if (prevStart == -1) {

        prevStart = currStart;

      }

    }

 

    return false;

  }

}

 

class Solution2 {

  public boolean patternMatch(String pattern, Iterator<String> it) {

    if (pattern == null || pattern.isEmpty() || it == null) {

      return false;

    }

 

    StringBuilder sb = new StringBuilder();

    while (it.hasNext()) {

      sb.append(it.next());

    }

 

    return strStr(sb.toString(), pattern);

  }

 

  private boolean strStr(String s, String t) {

 

    int[] lookup = preSuffix(t);

    int i = 0;

    int j = 0;

    while (i < s.length()) {

      if (s.charAt(i) == t.charAt(j)) {

        i++;

        j++;

      }

      else if (j == 0) {

        i++;

      }

      else {

        j = lookup[j];

      }

 

      if (j == t.length()) {

        return true;

      }

    }

 

    return false;

  }

 

  private int[] preSuffix(String t) {

    int[] lookup = new int[t.length()];

 

    int i = 1;

    int j = 0;

    while (i < t.length()) {

      if (t.charAt(i) == t.charAt(j)) {

        lookup[i] = j + 1;

        i++;

        j++;

      }

      else if (j == 0) {

        i++;

      }

      else {

        j = lookup[j];

      }

    }

 

    return lookup;

  }

}

Read full article from Google – Multiple Strings Pattern Matching