Skip to content

Latest commit

 

History

History
54 lines (45 loc) · 1.22 KB

0524-通过删除字母匹配到字典里最长单词.md

File metadata and controls

54 lines (45 loc) · 1.22 KB

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

示例 1:

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

输出: "apple" 示例 2:

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

输出: "a" 说明:

所有输入的字符串只包含小写字母。 字典的大小不会超过 1000。 所有输入的字符串长度不会超过 1000。

var findLongestWord = function(s, dictionary) {
  let res = ''
  let max = 0
  const len = s.length
  if (len === 0) return res
  for (let i = 0; i < dictionary.length; i++) {
    const cur = dictionary[i]
    let j = 0
    let k = 0
    let count = 0
    while(j < len && k < cur.length && cur.length - k + count >= max) {
      if (s[j] === cur[k]) {
        k++
        count++
      }
      j++
    }
    if (count !== cur.length) {
      count = 0
    }
    if ((max === count && cur < res) || max < count) {
      max = count
      res = cur
    }
  }

  return res
};

解题思路:两次循环找出匹配字符并且记录最小字符集