leetcode-go/hard/10.go

package main

import "fmt"

func isMatch(s string, p string) bool {
	// If former x chars of string matches former y chars
	// of pattern, match[x][y] == true, else == false
	var match [][]bool
	// Init match
	for i := 0; i < len(s)+1; i++ {
		row := make([]bool, len(p)+1)
		match = append(match, row)
	}
	// "" matches ""
	match[0][0] = true
	// Current & last char rank of pattern
	currP, lastP := 1, 0
	for currP <= len(p) {
		zeroOrMore := false
		// Current char of pattern
		charP := p[currP-1]
		if currP < len(p) && p[currP] == '*' {
			zeroOrMore = true
			currP++                           // To skip '*'
			match[0][currP] = match[0][lastP] // .* pattern can match len 0 string
		}
		// Start from the first char of string
		for currS := 1; currS <= len(s); currS++ {
			charS := s[currS-1]
			if !zeroOrMore {
				// s1s2...sx ~ p1p2...py <=> s1...s(x-1) ~ p1...p(x-1) && sx ~ py
				match[currS][currP] = match[currS-1][lastP] &&
					(charP == '.' || charS == charP)
			} else {
				// ... <=> s1...sx ~ p1...p(y-1) [ie. py matches nothing] ||
				// (sx ~ sy && s1...s(x-1) ~ p1...py)
				match[currS][currP] = match[currS][lastP] ||
					((charP == '.' || charS == charP) &&
						match[currS-1][currP])
			}
		}
		lastP = currP
		currP++
	}
	return match[len(s)][len(p)]
}

func main() {
	fmt.Println(isMatch("", ""))
	fmt.Println(isMatch("ssssss", "p"))
	fmt.Println(isMatch("ssssss", "s*"))
	fmt.Println(isMatch("ssssss", "s.*s"))
	fmt.Println(isMatch("ss", "s.*ss"))
	fmt.Println(isMatch("ss", "s*"))
}