通过删除字母匹配到字典里最长单词

给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。

  • 输入：s = “abpcplea”, dictionary = [“ale”,”apple”,”monkey”,”plea”]

  • 输出：”apple”

  • 输入：s = “abpcplea”, dictionary = [“a”,”b”,”c”]

  • 输出：”a”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
var findLongestWord = function(s, dictionary) {
    let ret = [];
    for (let i = 0; i < dictionary.length; i++) {
        let top = 0;
        let bottom = 0;
        while (top < s.length && bottom < dictionary[i].length) {
            if (s[top] == dictionary[i][bottom]) {
                bottom++;
            }
            top++;
        }
        if (bottom == dictionary[i].length) {
            ret.push(dictionary[i]);
        }
    }
    ret = ret.sort((a,b) => {
        if (a.length == b.length) {
            return dictSort(a, b);
        } else {
            return b.length - a.length;
        }
    })
    return ret[0] || '';
};

function dictSort(str1, str2) {
	let max = Math.max(str1.length, str2.length);
	for (let i = 0; i < max; i++) {
		let left = str1[i] !== undefined ? str1[i].charCodeAt() : -Infinity;
		let right = str2[i] !== undefined ? str2[i].charCodeAt() : -Infinity;
		if (left == right) {
			continue;
		}
		if (left < right) {
			return -1;
		} else {
			return 1;
		}
	}
	return 0;
}