動的計画法でドットとアスタリスクの入った型が文字列全体に合うか調べる

def fits(ch, pc):
    if ch is None:
        return False
    return pc in (ch, ".")


def step(prev, ch, p):
    row = [prev is None]
    for j, pc in enumerate(p):
        if pc == "*":
            v = row[j - 1]
            before = p[j - 1]
            if fits(ch, before):
                v |= prev[j + 1]
        else:
            v = fits(ch, pc)
            v = v and prev[j]
        row.append(v)
    return row


def pattern_match(s, p):
    row = step(None, None, p)
    for ch in s:
        row = step(row, ch, p)
    return row[-1]

function fits(ch, pc) {
  if (ch === null) {
    return false;
  }
  if (pc === ".") {
    return true;
  }
  return pc === ch;
}

function step(prev, ch, p) {
  const row = [prev === null];
  [...p].forEach((pc, j) => {
    let v;
    if (pc === "*") {
      v = row[j - 1];
      if (fits(ch, p[j - 1])) {
        v = v || prev[j + 1];
      }
    } else {
      v = fits(ch, pc);
      v = v && prev[j];
    }
    row.push(v);
  });
  return row;
}

function patternMatch(s, p) {
  let row = step(null, null, p);
  for (const ch of s) {
    row = step(row, ch, p);
  }
  return row[row.length - 1];
}

func fits(
	has bool, ch, pc byte,
) bool {
	if !has {
		return false
	}
	return pc == ch || pc == '.'
}

func step(
	prev []bool,
	ch byte, p string,
) []bool {
	has := prev != nil
	row := []bool{!has}
	for j := 0; j < len(p); j++ {
		pc := p[j]
		v := false
		if pc == '*' {
			v = row[j-1]
			if fits(has, ch, p[j-1]) {
				v = v || prev[j+1]
			}
		} else {
			v = fits(has, ch, pc) &&
				prev[j]
		}
		row = append(row, v)
	}
	return row
}

func patternMatch(
	s, p string,
) bool {
	row := step(nil, 0, p)
	for i := 0; i < len(s); i++ {
		row = step(row, s[i], p)
	}
	return row[len(p)]
}