Cracking Coding Interview - 16.18 Pattern Matching

Pattern Matching: You are given two strings, pattern and value.The pattern string consists of just the letters a and b, describing a pattern within a string. For example, the string catcatgocatgo matches the pattern aabab (where cat is a and go is b). It also matches patterns like a, ab, and b. Write a method to determine if value matches pattern.

Hints: #631, #643, #653, #663, #685, #718, #727

解法

理解一下题意：

1
2
3
4
5


Input    : catcatgocatgo
Pattern 1: aabab, a=cat, b=go
Pattern 2: a, a=catcatgocatgo
Pattern 3: ab, a=c, b=atcatgocatgo or a=ca, b=tcatgocatgo or ...
Pattern 4: b, b=catcatgocatgo

看一下Pattern 3 ab，其实只要在字符串中间切一刀，只要两边不相同就能够匹配ab。所以这个问题不是对单词（word）的模式匹配。

看Pattern 2 a和Pattern 4 b，这就说明a和b其实是等价的。

看Pattern 1aabab，前面已经说了这个问题不是对word的模式匹配，那么是如何得到a=cat、b=go的呢？

我们可以逐步检验Pattern，我们可以先看第一个a，那么Pattern实际上就变成了a|abab。然后我们开始猜测a：

1
2
3
4
5


c|atcatgocatgo
ca|tcatgocatgo
cat|catgocatgo
catc|atgocatgo
...

我们可以先用第一个选择，把a=c，然后就看Pattern的第二个a|bab，检验atcatgocatgo，因为已知a=c，这个就很好检验，发现检验结果失败。

然后以此类推。这个过程可以描述为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


matchPattern(catcatgocatgo, aabab)
  matchPattern(catcatgocatgo, aabab, a=c, b=)
    matchPattern(atcatgocatgo, abab, a=c, b=)
      return false
  matchPattern(catcatgocatgo, aabab, a=ca, b=)
    matchPattern(tcatgocatgo, abab, a=ca, b=)
      return false;
  matchPattern(catcatgocatgo, aabab, a=cat, b=)
    matchPattern(catgocatgo, abab, a=cat, b=)
      matchPattern(gocatgo, bab, a=cat, b=)
        matchPattern(gocatgo, bab, a=cat, b=g)
          matchPattern(ocatgo, ab, a=cat, b=g)
            return false
        matchPattern(gocatgo, bab, a=cat, b=go)
          matchPattern(catgo, ab, a=cat, b=go)
            matchPattern(go, b, a=cat, b=go)
              matchPattern("", "", a=cat, b=go)
                return true

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


public boolean matches(String value, String pattern, String prefixA, String prefixB) {
  if (value == "" && pattern == "") {
    // 匹配完毕，说明成功了
    return true;
  }
  if (value == "" || pattern == "") {
    return false;
  }
  char patternChar = pattern.charAt(0);
  if (patternChar == 'a') {
    // 现在检查的是a
    if (prefixA != null) {
      if (!value.startsWith(prefixA)) {
        return false;
      }
      // 去掉value的prefixA，去掉pattern的当前字符，然后继续比较
      return matches(value.subString(prefixA.length()), pattern.subString(1), prefixA, prefixB);
    } else {
      boolean result = false;
      for (int i = 1; i <= value.length(); i++) {
        prefixA = value.subString(0, i);
        result = result || matches(value, pattern, prefixA, prefixB);
      }
      return result;
    }
  }
  
  if (patternChar == 'b') {
    if (prefixB != null) {
      if (!value.startsWith(prefixB)) {
        return false;
      }
      return matches(value.subString(prefixB.length()), pattern.subString(1), prefixA, prefixB);
    } else {
      boolean result = false;
      for (int i = 1; i <= value.length(); i++) {
        prefixB = value.subString(0, i);
        result = result || matches(value, pattern, prefixA, prefixB);
      }
      return result;
    }
  }
}

时间复杂度：太复杂，计算不出来。

解法2（更好）

还是看这个：

1
2


Value:   catcatgocatgo
Pattern: aabab

我们可以看到a有3个，b有2个，Value的长度为13，那么可以知道a的最长的长度是13 / 3 = 4，因此可以缩小a的取值范围，b的长度则等于(13 - 3 * a) / 2。可以依此猜测a和b的值，然后看是否匹配。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46


public boolean patternMatches(String value, String pattern) {
  // pattern的第一个字符就是mainChar，另一个则是subChar
  char mainChar = pattern.charAt(0);
  // mainChar的数量
  int mainCount = mainChar == 'a' ? count(pattern, 'a') : count(pattern, 'b');
  // subChar的数量
  int subCount = pattern.length() - mainCount;
  // mainChar所代表的字符串的最大长度
  int maxMainSize = mainCount == 0 ? 0 : value.length() / mainCount;
  
  int firstSubIndex = pattern.indexOf(subChar);  
  
  // 尝试所有mainChar所代表的字符串的长度
  for (int mainSize = 0; mainSize <= maxMainSize; i++) {
    // 计算得到subChar所代表字符串的长度
    int subSize = (value.length() - mainCount * mainSize) / subCount;
    if (subSize * subCount + mainSize * mainCount != value.length()) {
      // 这种组合不等于value的长度
      continue;
    }
    
    String main = value.subString(0, mainSize);
    // 跳过头部的几个mainChar所代表的字符串，得到subChar代表的字符串。
    String sub = value.subString(mainSize * firstSubIndex, mainSize * firstSubIndex + subSize);
    // 根据pattern构建预期的字符串
    String expected = build(pattern, main, mainCount, sub, subCount);
    if (value.equals(expected)) {
      return true;
    }
  }
  return false;
}

private String build(String pattern, String main, String sub) {
  StringBuilder sb = new StringBuilder();
  char mainChar = pattern.charAt(0);
  for (int i = 0; i < pattern.length(); i++) {
    char curr = pattern.charAt(i);
    if (curr == mainChar) {
      sb.append(main);
    } else {
      sb.append(sub);
    }
  }
  return sb.toString();
}

时间复杂度：

尝试所有main的可能性为n次（n为value的长度），即n个循环。每个循环里：
- 构建预期字符串的循环为m次（m为pattern的长度）
- 判断预期字符串和value是否相等的复杂度为O(n)（n为value的长度）
所以时间复杂度为O(n²)，最坏情况下m=n。

Cracking Coding Interview - 16.18 Pattern Matching

解法

解法2（更好）

版权

评论

Cracking Coding Interview - 16.18 Pattern Matching

解法

解法2（更好）

版权

相关文章

评论