524.go

package problem

/*
### 题目:

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


#### 示例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: 反正题目没有要求,来个正则吧,符合正则匹配的,都撸出来!

*/

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
}