leetcode面试题16.18模式匹配

前言

又是好久没有更新了

正文

问题来源

本问题来自leetcode上的面试题16.18题。

问题描述

你有两个字符串，即pattern和value。 pattern字符串由字母”a”和”b”组成，用于描述字符串中的模式。例如，字符串”catcatgocatgo”匹配模式”aabab”（其中”cat”是”a”，”go”是”b”），该字符串也匹配像”a”、”ab”和”b”这样的模式。但需注意”a”和”b”不能同时表示相同的字符串。编写一个方法判断value字符串是否匹配pattern字符串。

示例 1:

输入： pattern = "abba", value = "dogcatcatdog"
输出： true

示例 2:

输入： pattern = "abba", value = "dogcatcatfish"
输出： false

示例 3:

输入： pattern = "aaaa", value = "dogcatcatdog"
输出： false

示例 4:

输入： pattern = "abba", value = "dogdogdogdog"
输出： true
解释： "a"="dogdog",b=""，反之也符合规则

分析：

思想是先控制a,b的长度，可以决定从哪里进行字符串匹配
很容易得到a解析长度范围[0, len(value)/ac]，其中ac是a出现的个数（得注意ac为0的情况）；根据a的长度可以计算出b的长度为(len(value) - ac * al) / bc（得注意bc为0的情况）；根据pattern串对比循环匹配，当前匹配上后向后移动相应距离，没匹配则break掉内层循环；当内层循环结束后，判断是否处理到value的末尾并且得到的a，b不相等，返回true；一直都无返回true则代表匹配失败，返回false。

func patternMatching(pattern string, value string) bool {
    ac, bc := 0, 0
    for _, v := range pattern {
        if v == 'a' {
            ac++
        }
    }
    bc = len(pattern) - ac
    if value == "" {
        if ac == 0 || bc == 0 {
            return true
        }
        return false // value == "" pattern中既有ab，则代表a,b都为"",按照ab不相等原则应该返回false
    }
    //al, bl := 0, 0
    avg := 0
    if ac != 0 {
        avg = len(value)/ac
    }
    for al := 0; al <= avg; al++ {
        bl := 0
        if bc != 0 {
            bl = (len(value) - ac * al) / bc
        }
        if len(value) - ac * al - bc * bl != 0 {
            continue
        } 
        a, b := "", ""
        index := 0
        for i := 0; i < len(pattern); i++ {
            if pattern[i] == 'a' {
                if a == "" {
                    a = string(value[index:index+al])
                    index += al
                } else {
                    if a != string(value[index:index+al]) {
                        break
                    }
                    index += al
                }
            } else if pattern[i] == 'b' {
                if b == "" {
                    b = string(value[index:index+bl])
                    index += bl
                } else {
                    if b != string(value[index:index+bl]) {
                        break
                    }
                    index += bl
                }
            }           
        }
        if index == len(value) && a != b {
            return true
        }
    }
    return false  
}

总结：

勤思考。

结语

不管怎么样好好加油。

leetcode Interview Question 16.18 Pattern Match

前言

正文