最近我把做过的题目 题解+思路+代码+代码注释 都放到了 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的时候,先用m在s里找,发现s里一个m都木有,那么,monkey肯定不匹配
首先要注意,可能字符串是空,或者字典也可能是空的
其次, 符合的答案可能是多个,那么,多个的时候,先按照长度最长判断,长度相同的时候,按照字典序最小的! 注意这个字典序并不是 上面示例中的 d数组里的value所对应的 key,字典序是按照 字母的顺序排列的, 比如 a 肯定是在 c 前面的!
因为我是用Golang解题,那么,Golang的 sort字符串排序就是按照字典顺序排列的!
思路:
大致解法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)已重构,代码开源
