-
Notifications
You must be signed in to change notification settings - Fork 40
/
LongestWordInDictionaryThroughDeleting.js
64 lines (60 loc) · 1.7 KB
/
LongestWordInDictionaryThroughDeleting.js
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// Source : https://leetcode.com/problems/longest-word-in-dictionary-through-deleting
// Author : Dean Shi
// Date : 2017-03-08
/***************************************************************************************
*
* Given a string and a string dictionary, find the longest string in the dictionary
* that can be formed by deleting some characters of the given string. If there are
* more than one possible results, return the longest word with the smallest
* lexicographical order. If there is no possible result, return the empty string.
*
* Example 1:
*
* Input:
* s = "abpcplea", d = ["ale","apple","monkey","plea"]
*
* Output:
* "apple"
*
* Example 2:
*
* Input:
* s = "abpcplea", d = ["a","b","c"]
*
* Output:
* "a"
*
* Note:
*
* All the strings in the input will only contain lower-case letters.
* The size of the dictionary won't exceed 1,000.
* The length of all the strings in the input won't exceed 1,000.
*
*
***************************************************************************************/
/**
* @param {string} s
* @param {string[]} d
* @return {string}
*/
var findLongestWord = function(s, d) {
let dir = d.sort((a, b) => b.length - a.length)
let result = []
let longestLen = 0
for (let i = 0; i < dir.length; i++) {
if (longestLen > dir[i].length) break;
if (helper(s, dir[i])) {
longestLen = dir[i].length
result.push(dir[i])
}
}
return result.length ? result.sort()[0] : ''
};
function helper(s, t) {
if (t.length === 0) return true
if (s.length === 0) return false
if (s[0] === t[0]) {
return helper(s.substring(1), t.substring(1))
}
return helper(s.substring(1), t)
}