Question

16.18. Pattern Matching

中文文档

Description

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. a and b cannot be the same string.

Example 1:

Input:  pattern = "abba", value = "dogcatcatdog"

Output:  true

Example 2:

Input:  pattern = "abba", value = "dogcatcatfish"

Output:  false

Example 3:

Input:  pattern = "aaaa", value = "dogcatcatdog"

Output:  false

Example 4:

Input:  pattern = "abba", value = "dogdogdogdog"

Output:  true

Explanation:  "a"="dogdog",b=""，vice versa.

Note:

• 0 <= len(pattern) <= 1000
• 0 <= len(value) <= 1000
• pattern only contains "a" and "b", value only contains lowercase letters.

Solutions

Solution 1: Enumeration

We first count the number of characters 'a' and 'b' in the pattern string $pattern$, denoted as $cnt[0]$ and $cnt[1]$, respectively. Let the length of the string $value$ be $n$.

If $cnt[0]=0$, it means that the pattern string only contains the character 'b'. We need to check whether $n$ is a multiple of $cnt[1]$, and whether $value$ can be divided into $cnt[1]$ substrings of length $n/cnt[1]$, and all these substrings are the same. If not, return $false$ directly.

If $cnt[1]=0$, it means that the pattern string only contains the character 'a'. We need to check whether $n$ is a multiple of $cnt[0]$, and whether $value$ can be divided into $cnt[0]$ substrings of length $n/cnt[0]$, and all these substrings are the same. If not, return $false$ directly.

Next, we denote the length of the string matched by the character 'a' as $la$, and the length of the string matched by the character 'b' as $lb$. Then we have $la \times cnt[0] + lb \times cnt[1] = n$. If we enumerate $la$, we can determine the value of $lb$. Therefore, we can enumerate $la$ and check whether there exists an integer $lb$ that satisfies the above equation.

The time complexity is $O(n^2)$, and the space complexity is $O(n)$. Here, $n$ is the length of the string $value$.

class Solution:
  def patternMatching(self, pattern: str, value: str) -> bool:
    def check(la: int, lb: int) -> bool:
      i = 0
      a, b = "", ""
      for c in pattern:
        if c == "a":
          if a and value[i : i + la] != a:
            return False
          a = value[i : i + la]
          i += la
        else:
          if b and value[i : i + lb] != b:
            return False
          b = value[i : i + lb]
          i += lb
      return a != b

    n = len(value)
    cnt = Counter(pattern)
    if cnt["a"] == 0:
      return n % cnt["b"] == 0 and value[: n // cnt["b"]] * cnt["b"] == value
    if cnt["b"] == 0:
      return n % cnt["a"] == 0 and value[: n // cnt["a"]] * cnt["a"] == value

    for la in range(n + 1):
      if la * cnt["a"] > n:
        break
      lb, mod = divmod(n - la * cnt["a"], cnt["b"])
      if mod == 0 and check(la, lb):
        return True
    return False

class Solution {
  private String pattern;
  private String value;

  public boolean patternMatching(String pattern, String value) {
    this.pattern = pattern;
    this.value = value;
    int[] cnt = new int[2];
    for (char c : pattern.toCharArray()) {
      ++cnt[c - 'a'];
    }
    int n = value.length();
    if (cnt[0] == 0) {
      return n % cnt[1] == 0 && value.substring(0, n / cnt[1]).repeat(cnt[1]).equals(value);
    }
    if (cnt[1] == 0) {
      return n % cnt[0] == 0 && value.substring(0, n / cnt[0]).repeat(cnt[0]).equals(value);
    }
    for (int la = 0; la <= n; ++la) {
      if (la * cnt[0] > n) {
        break;
      }
      if ((n - la * cnt[0]) % cnt[1] == 0) {
        int lb = (n - la * cnt[0]) / cnt[1];
        if (check(la, lb)) {
          return true;
        }
      }
    }
    return false;
  }

  private boolean check(int la, int lb) {
    int i = 0;
    String a = null, b = null;
    for (char c : pattern.toCharArray()) {
      if (c == 'a') {
        if (a != null && !a.equals(value.substring(i, i + la))) {
          return false;
        }
        a = value.substring(i, i + la);
        i += la;
      } else {
        if (b != null && !b.equals(value.substring(i, i + lb))) {
          return false;
        }
        b = value.substring(i, i + lb);
        i += lb;
      }
    }
    return !a.equals(b);
  }
}

class Solution {
public:
  bool patternMatching(string pattern, string value) {
    int n = value.size();
    int cnt[2]{};
    for (char c : pattern) {
      cnt[c - 'a']++;
    }
    if (cnt[0] == 0) {
      return n % cnt[1] == 0 && repeat(value.substr(0, n / cnt[1]), cnt[1]) == value;
    }
    if (cnt[1] == 0) {
      return n % cnt[0] == 0 && repeat(value.substr(0, n / cnt[0]), cnt[0]) == value;
    }
    auto check = [&](int la, int lb) {
      int i = 0;
      string a, b;
      for (char c : pattern) {
        if (c == 'a') {
          if (!a.empty() && a != value.substr(i, la)) {
            return false;
          }
          a = value.substr(i, la);
          i += la;
        } else {
          if (!b.empty() && b != value.substr(i, lb)) {
            return false;
          }
          b = value.substr(i, lb);
          i += lb;
        }
      }
      return a != b;
    };
    for (int la = 0; la <= n; ++la) {
      if (la * cnt[0] > n) {
        break;
      }
      if ((n - la * cnt[0]) % cnt[1] == 0) {
        int lb = (n - la * cnt[0]) / cnt[1];
        if (check(la, lb)) {
          return true;
        }
      }
    }
    return false;
  }

  string repeat(string s, int n) {
    string ans;
    while (n--) {
      ans += s;
    }
    return ans;
  }
};

func patternMatching(pattern string, value string) bool {
  cnt := [2]int{}
  for _, c := range pattern {
    cnt[c-'a']++
  }
  n := len(value)
  if cnt[0] == 0 {
    return n%cnt[1] == 0 && strings.Repeat(value[:n/cnt[1]], cnt[1]) == value
  }
  if cnt[1] == 0 {
    return n%cnt[0] == 0 && strings.Repeat(value[:n/cnt[0]], cnt[0]) == value
  }
  check := func(la, lb int) bool {
    i := 0
    a, b := "", ""
    for _, c := range pattern {
      if c == 'a' {
        if a != "" && value[i:i+la] != a {
          return false
        }
        a = value[i : i+la]
        i += la
      } else {
        if b != "" && value[i:i+lb] != b {
          return false
        }
        b = value[i : i+lb]
        i += lb
      }
    }
    return a != b
  }
  for la := 0; la <= n; la++ {
    if la*cnt[0] > n {
      break
    }
    if (n-la*cnt[0])%cnt[1] == 0 {
      lb := (n - la*cnt[0]) / cnt[1]
      if check(la, lb) {
        return true
      }
    }
  }
  return false
}

function patternMatching(pattern: string, value: string): boolean {
  const cnt: number[] = [0, 0];
  for (const c of pattern) {
    cnt[c === 'a' ? 0 : 1]++;
  }
  const n = value.length;
  if (cnt[0] === 0) {
    return n % cnt[1] === 0 && value.slice(0, (n / cnt[1]) | 0).repeat(cnt[1]) === value;
  }
  if (cnt[1] === 0) {
    return n % cnt[0] === 0 && value.slice(0, (n / cnt[0]) | 0).repeat(cnt[0]) === value;
  }
  const check = (la: number, lb: number) => {
    let i = 0;
    let a = '';
    let b = '';
    for (const c of pattern) {
      if (c === 'a') {
        if (a && a !== value.slice(i, i + la)) {
          return false;
        }
        a = value.slice(i, (i += la));
      } else {
        if (b && b !== value.slice(i, i + lb)) {
          return false;
        }
        b = value.slice(i, (i += lb));
      }
    }
    return a !== b;
  };
  for (let la = 0; la <= n; ++la) {
    if (la * cnt[0] > n) {
      break;
    }
    if ((n - la * cnt[0]) % cnt[1] === 0) {
      const lb = ((n - la * cnt[0]) / cnt[1]) | 0;
      if (check(la, lb)) {
        return true;
      }
    }
  }
  return false;
}