# __ .______ __ __ .______ .___________. ______ ______ .___ ___. # | | | _ \ | | | | | _ \ | | / | / __ \ | \/ | # | | | |_) | | |__| | | |_) | `---| |----` | ,----'| | | | | \ / | # | | | ___/ | __ | | ___/ | | | | | | | | | |\/| | # | | | | | | | | | | | | __ | `----.| `--' | | | | | # |__| | _| |__| |__| | _| |__| (__) \______| \______/ |__| |__| # ""$o o$"" ""$o o$" o "$""""o "o $" o""" $" "$o "$o" $o " $ o$" "$o $$$o$$$$o$$$$ $" "oooo o "" ""$$$$$$$$""o"" oo oooo" "$$$$$$oo"oo$$$o" o$$$$oo" o$$$o "o$$$$$$$ "$ $$$$$$$$$oo o$$$$$$$$$o"$" $ $$$ $$$$$$ o$$$$$$ "$$o"o $ $$$$o $$$$$$ $$$$$$$ $$$$o"o $ $$$$$ $$$$$" "$$$$$ $$$$$$ $ $o""""" """" """ """"""$" $ o$$$$$"""$$$$$"$$$$$""$$$$$ooo"o $ o"$o $$$$$$$$oo$$$$$$$$o $$"" $ oo$ "$$$$$$$$$$$$$$$$$$$$" o" o $oo o$$$"$ $$o"o $$$$$$$"" "$$$$$$$ o$$ $$$$o IPHPT BUG o$$$$" $ $$$$ o "$$$$$oo o$$$$$$ "o$$$$ $ $$$$$ o$$"" $ $$$$$o" "$$$$$$$$$$$$$ o o$$$$$o$ "" $$ $$" $ $$$" o"o$$$$$$$$$$$$ " "$$$ $ $$o o$$ "o $$ " $$$$$$$$$$$"o "$$ $ $$$ $$$ oo$ $ o""$$""$$$o " $"o$o $$$o o$$$$ o$$$"o"$oo$$$$o" o $o $$$$$oo$ $$$$o $$$$ $$$$ $$$$" $ $$$$$"" $$ o$$$ """$$$$"o" "$$$o "$$$o $$$" o """ $ $$$oo $$$$o" $$ o$$$"o" """"$ o$$$ o$" $$$ $ "$"" o$"o"$$o$$$$ "$$"o" o$$ "$oo $ " $$o $ "oo$"o$$$"o$o"$$$$o" o" $$$ ""$o $$ $$$o "o$$o$"$$"$$o$$o$$"$$o" $$$ ""o $$$ ""$$$ $$$$$$ $$$$ $" $$$$ $$ $$$$ $$$$"$$$o$ $"" $$$ $$$$ "$$$ """ $$$$ $$"" "$$ oo$" $ooo $ "$$ 524. 通过删除字母匹配到字典里最长单词(题目解析+思路分析+代码行注释)   -  叶落山城秋

524. 通过删除字母匹配到字典里最长单词(题目解析+思路分析+代码行注释)

最近我把做过的题目 题解+思路+代码+代码注释 都放到了 github上,有需要的自取 github地址

题目:

给定一个字符串和一个字符串字典,找到字典里面最长的字符串,该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个,返回长度最长且字典顺序最小的字符串。如果答案不存在,则返回空字符串。

示例1:

输入:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

输出: 
"apple"

示例2:

输入:
s = "abpcplea", d = ["a","b","c"]

输出: 
"a"

解析题目:

以示例1来说, 比如 ale来匹配 s,先把 a字母放到s里找,发现s里第一个就是,那么,按照顺序,开始用l来找,且在s里第二个开始找(因为顺序是固定的),发现在s的下标5处找到了l,然后开始用e来找且从s下标5后面开始找,发现s下标6就是e,然后ale全部找到了,那么说明 ale是答案之一,apple同理,到monkey的时候,先用ms里找,发现s里一个m都木有,那么,monkey肯定不匹配

首先要注意,可能字符串是空,或者字典也可能是空的

其次, 符合的答案可能是多个,那么,多个的时候,先按照长度最长判断,长度相同的时候,按照字典序最小的! 注意这个字典序并不是 上面示例中的 d数组里的value所对应的 key,字典序是按照 字母的顺序排列的, 比如 a 肯定是在 c 前面的!

因为我是用Golang解题,那么,Golangsort字符串排序就是按照字典顺序排列的!

思路:

大致解法1: 粗暴的拿d里的每个字符串的每个字母依次跟 s的每个字母进行比较! 不过得注意顺序

大致解法2: 根据d的字符串的每个字母在s里进行匹配,s里多余的都删掉,得最后结果

大致解法3: 反正题目没有要求,来个正则吧,符合正则匹配的,都撸出来!

代码:

已写解法1和解法3的代码,可惜解法3时间超出限制了..

解法1代码:

func findLongestWord(s string, d []string) string {
	if s == "" || len(d) == 0 {
		return ""
	}
	var res string
	for _,v := range d {
	    // 如果字典字符串比s还要长,那么肯定匹配不上
		if len(v) > len(s) {
			continue
		}
		i := 0
		j := 0
		for i<len(v) && j < len(s) {
			if v[i] == s[j] {
			    // 当匹配到一个字符后,如果后面的长度比被匹配的还要长,那么肯定匹配不上
				if len(v[i:]) > len(s[j:]) {
					break
				}
				i++
			}
			j++
		}
		// 如果i 等于v的长度,说明 v已经完全匹配了,那么说明它肯定是s的子集
		if i == len(v) {
		    // 比较之前最符合的子集长度与此次的相比
			if len(v) == len(res) {
			    // 直接按照 大小比字典顺序
				 if v < res {
                    res = v
                 }
			} else if len(v) > len(res) {
				res = v
			}
		}
	}

	return res
}

解法3:

这个解法在leetcode上直接超出时间限制了..估计数量太大..

func findLongestWord(s string, d []string) string {

    res := make(map[int]int)
    
    // 循环d
	for k,v := range d {
		if len(v) > len(s) {
			continue
		}
		// 把d里每个字符串都切割成一个匹配的正则表达式
		var buffer bytes.Buffer
		buffer.WriteString("(.*)")
		for i := 0; i < len(v); i++ {
			buffer.WriteString(string(v[i]))
			buffer.WriteString("(.*)")
		}
		reg := buffer.String()
		rgx := regexp.MustCompile(reg)
		// 看是否匹配,如果匹配,就丢到数组里
		match := rgx.MatchString(s)
		if match {
			res[k] = len(v)
		}
	}

	var test []string
	mapKey := -1
	var mapValue string
	for m,n := range res {
		if n != 0 {
			test = append(test,d[m])
			if mapKey == -1 {
				mapKey = n
				mapValue = d[m]
				continue
			}
			if mapKey < n {
				mapKey = n
				mapValue = d[m]
			} else if mapKey == n {
				arr := []string{mapValue,d[m]}
				sort.Sort(sort.StringSlice(arr))
				mapValue = arr[0]
			}
		}
	}
	
	return mapValue
}

欢迎转载,但请附上原文地址哦,尊重原创,谢谢大家 本文地址: https://www.iphpt.com/detail/134/
本站(PHP --> Golang)已重构,代码开源

当你能力不能满足你的野心的时候,你就该沉下心来学习