No-recursive solution in golang. only 3ms


  • 0
    X

    My solution have no overhead for recursive. it just take 3ms
    Key point is when match "*" character, record next possibility in to table and continue to match.
    If false finally, restart whole search with record(i and j) of table

    type data struct {
    	i int
    	j int
    }
    
    func isMatch(s string, p string) bool {
    	i := len(s) - 1
    	j := len(p) - 1
    	next := make([]data, 0, 10)
    	for i >= 0 || j >= 0 {
    		if j >= 0 {
    			c := p[j]
    			switch c {
    			case '.':
    				if i >= 0 {
    					j--
    					i--
    					continue
    				}
    			case '*':
    				if i == -1 || (p[j-1] != '.' && p[j-1] != s[i]) {
    					j -= 2
    					continue
    				}
    				next = append(next, data{i - 1, j})
    				j -= 2
    				continue
    			default:
    				if i >= 0 && p[j] == s[i] {
    					i--
    					j--
    					continue
    				}
    			}
    		}
    		if len(next) != 0 {
    			i = next[len(next)-1].i
    			j = next[len(next)-1].j
    			next = next[:len(next)-1]
    			continue
    		}
    		return false
    	}
    	return true
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.