下面我给出一个具体的例子。
原题是 LC: 291 word pattern 2.

Given a pattern and a string s, return true if s matches the pattern.

A string s matches a pattern if there is some bijective mapping of single characters to non-empty strings such that if each character in pattern is replaced by the string it maps to, then the resulting string is s. A bijective mapping means that no two characters map to the same string, and no character maps to two different strings.

比如input是pattern = "abab", s = "redblueredblue"。那么output应该是true。因为a=red，b=blue可以match。（还有其它情况也可以match)
那么这个题我的思路是： 假设pattern有t个字符，那么我们需要做的是把s切成t份然后一一比较。那么，如何把一个数组切成t份呢？其实这就是一个组合问题。我们需要找到t-1个分割符号。假设s的长度是n。那么其实就是从n-1个数字中挑选t-1个。

下面是枚举所有组合的算法。

#include <cassert>
#include <functional>
#include <span>

void GenerateTCombination(uint32_t n, uint32_t t, const std::function<void(std::span<const uint32_t>)>& f) {
  assert(n >= t);
  // The numbers in the span that `f` visits are always in decreasing order.
  // Here we will store it in reversed order. For example, if n=5 and t=3, the first seq to visit is:{2,1,0}.
  // Then we will store it as {0,1,2} instead.
  // c[t] and c[t+1] are two sentinels at the end.
  std::vector<uint32_t> c(t + 2);
  // Initialize the vector c[0,...,n] in increasing order
  for (uint32_t j = 0; j < t; ++j) {
    c[j] = j;
  }
  c[t] = n;
  c[t + 1] = 0;
  // So, if n=5,t=3, now the content in C is {0,1,2,5,0}

  while (true) {
    f(std::span<const uint32_t>(c.begin(), c.begin() + t));
    // In the next we will increase the seq {c[t-1], c[t-2], ...,c[0]} by a small amount
    uint32_t j = 0;
    // Find the first one that can be increased
    for (; c[j] + 1 == c[j + 1]; ++j) {
      // reset c[j] to the smallest possible value
      c[j] = j;
    }
    if (j >= t) return;
    // Increase c[j]
    ++c[j];
  }
}

在此基础上，我做了一个稍稍的改进。我让回调函数f返回一个index。 如果index=0那么就代表停止遍历。如果index=1，那么就代表我们需要对刚刚返回的那个序列的第一个元素进行增加。如此类推。

bool GenerateTCombination(uint32_t n, uint32_t t, const std::function<size_t(std::span<const uint32_t>)>& f) {
  assert(n >= t);
  // The numbers in the span that `f` visits are always in decreasing order.
  // Here we will store it in reversed order. For example, if n=5 and t=3, the first seq to visit is:{2,1,0}.
  // Then we will store it as {0,1,2} instead.
  // c[t] and c[t+1] are two sentinels at the end.
  std::vector<uint32_t> c(t + 2);
  // Initialize the vector c[0,...,n] in increasing order
  for (uint32_t j = 0; j < t; ++j) {
    c[j] = j + 1;
  }
  c[t] = n + 1;
  c[t + 1] = 0;
  // So, if n=5,t=3, now the content in C is {0,1,2,5,0}

  while (true) {
    size_t ret = f(std::span<const uint32_t>(c.begin(), c.begin() + t));
    if (ret == 0) return false;
    --ret;
    //  In the next we will increase the seq {c[t-1], c[t-2], ...,c[0]} by a small amount
    uint32_t j = 0;
    // Find the first one that can be increased
    for (; c[j] + 1 == c[j + 1] || j + 1 < ret; ++j) {
      // reset c[j] to the smallest possible value
      c[j] = j + 1;
    }
    if (j >= t) return true;
    // Increase c[j]
    ++c[j];
  }
  return true;
}

下面是用改进后的GenerateTCombination函数解决leetcode中的这个问题：

bool wordPatternMatch(const std::string& pattern, std::string_view s) {
  if (pattern.empty() || pattern.size() > s.size()) return false;
  if (pattern.size() == 1) return true;
  return !GenerateTCombination(
      s.size() - 1, pattern.size() - 1, [&pattern, s](std::span<const uint32_t> separators) -> size_t {
        // return false if we found a match
        std::unordered_map<char, std::string_view> m;
        std::unordered_map<std::string_view, char> m2;
        size_t i = pattern.size();
        while (i > 0) {
          --i;
          char c = pattern[i];
          auto iter = m.find(c);
          size_t begin_index = i == 0 ? 0 : separators[i - 1];
          size_t len = (i + 1 == pattern.size()) ? s.size() - begin_index : separators[i] - begin_index;
          if (iter == m.end()) {
            auto iter2 = m2.find(s.substr(begin_index, len));
            if (iter2 != m2.end()) {
              if (iter2->second != c) {
                // No match. Jump out of this for loop and try next separators set
                return i + 1;
              }
              continue;
            }
            if (i == 0) {
              break;
            }
            m[c] = s.substr(begin_index, len);
            m2[s.substr(begin_index, len)] = c;
            continue;
          }
          if (len != iter->second.length() || !s.substr(begin_index).starts_with(iter->second)) return i + 1;
        }
        return 0;
      });
}

※ 修改:·snnn 于 Nov  4 06:34:41 2024 修改本文·[FROM: 61.172.164.*]
※ 来源:·水木社区 http://www.mysmth.net·[FROM: 61.172.164.*]

修改:snnn FROM 61.172.164.*
FROM 61.172.164.*