题目

题解

读题！读题！读题！读懂题意才能程序怎吗写。不是傻逼一样看一遍题目，看一遍例题就开始写程序。
这道题的题目指出，现有个一个字符串s和一个字典数组。要在这个字典数组中匹配出与该字符串s相似度最高的一个。但是字典中的字符串不是啥字符串都行，必须是字符串s的子串，啥是子串，题目给出的，该字符串可以通过删除 s 中的某些字符得到。明确规定，子串的长度不能超过字符串s的长度且不能包含字符串s中意外的字符，当两个子串拥有字符数量一样的时候就要字典序最小的那个。何为字典序，可以简单理解为字符的ASCLL码，看谁的ASCLL码小就选择谁。

双指针+循环

/**
 * @param {string} s
 * @param {string[]} dictionary
 * @return {string}
 * 条件一: 该字符串可以通过删除 s 中的某些字符得到 
 * 解释： 也就是说dictionary中的字符串必须是s的子串， 是字符串s经过删除部分字符 得到的
* 条件2: 返回长度最长且字典序最小的字符串
* 解释 返回子串中长度最长的，当子串中长度一致时，看谁的ASCLL小
 */
var findLongestWord = function(s, dictionary) {
    let prevLen = 0;
    let word = ''
    // 先把符合条件的子串筛选出来
    for(let value of dictionary) {
        let curValueLen = value.length;
        if(childWord(s, value)){
            if(curValueLen > prevLen) {
                prevLen = curValueLen;
                word = value
            } else if (curValueLen == prevLen) {
                if(value < word) word = value;
            }
        } 
    }
    return word;
};
/**
* 查找子串
* 当d中的字符没有出现在s中的字符说明不是它的字串
 */
function childWord (s, d) {
    let sLen = s.length;
    let dLen = d.length;
    let l = 0;
    let r = 0;
    while(r < dLen && l < sLen) {
        if(s[l] == d[r]) {
            r++;
        }
        l++;
    }
    return r == dLen
}

优化后的代码

/**
 * @param {string} s
 * @param {string[]} dictionary
 * @return {string}
 * 条件一: 该字符串可以通过删除 s 中的某些字符得到 
 * 解释： 也就是说dictionary中的字符串必须是s的子串， 是字符串s经过删除部分字符 得到的
* 条件2: 返回长度最长且字典序最小的字符串
* 解释 返回子串中长度最长的，当子串中长度一致时，看谁的ASCLL小
 */
var findLongestWord = function(s, dictionary) {
    let prevLen = 0;
    let word = ''
    // 先把符合条件的子串筛选出来
    for(let value of dictionary) {
        let curValueLen = value.length;
        if(childWord(s, value)){
            if(curValueLen > prevLen || (curValueLen == prevLen && value < word)) {
                prevLen = curValueLen;
                word = value
            }
        } 
    }
    return word;
};
/**
* 查找子串
* 当d中的字符没有出现在s中的字符说明不是它的字串
 */
function childWord (s, d) {
    let sLen = s.length;
    let dLen = d.length;
    let l = 0;
    let r = 0;
    while(r < dLen && l < sLen) {
        if(s[l] == d[r]) {
            r++;
        }
        l++;
    }
    return r == dLen
}

再次优化

/**
 * @param {string} s
 * @param {string[]} dictionary
 * @return {string}
 * 条件一: 该字符串可以通过删除 s 中的某些字符得到 
 * 解释： 也就是说dictionary中的字符串必须是s的子串， 是字符串s经过删除部分字符 得到的
* 条件2: 返回长度最长且字典序最小的字符串
* 解释 返回子串中长度最长的，当子串中长度一致时，看谁的ASCLL小
 */
var findLongestWord = function(s, dictionary) {
    let prevLen = 0;
    let word = ''
    // 先把符合条件的子串筛选出来
    for(let value of dictionary) {
        let curValueLen = value.length;
        if(childWord(s, value)){
            if(curValueLen > prevLen || (curValueLen == prevLen && value < word)) {
                prevLen = curValueLen;
                word = value
            }
        } 
    }
    return word;
};
/**
* 查找子串
* 当d中的字符没有出现在s中的字符说明不是它的字串
 */
function childWord (s, d) {
    let sLen = s.length;
    let dLen = d.length;
    if(sLen < dLen) return false
    let l = 0;
    let r = 0;
    while(r < dLen && l < sLen) {
        if(s[l] == d[r]) r++;
        l++;
    }
    return r == dLen;
}

双指针+排序

/**
 * @param {string} s
 * @param {string[]} dictionary
 * @return {string}
 * 条件一: 该字符串可以通过删除 s 中的某些字符得到 
 * 解释： 也就是说dictionary中的字符串必须是s的子串， 是字符串s经过删除部分字符 得到的
* 条件2: 返回长度最长且字典序最小的字符串
* 解释 返回子串中长度最长的，当子串中长度一致时，看谁的ASCLL小
 */
var findLongestWord = function(s, dictionary) {
    dictionary.sort()
    dictionary.sort((a,b) => b.length - a.length);
    for(value of dictionary) {
        if(childWord(s, value)) {
            return value
        }
    }
    return ''
};
/**
* 判断是否为子串
 */
function childWord (s, d) {
    let sLen = s.length;
    let dLen = d.length;
    let l = 0;
    let r = 0;
    while(r < dLen && l < sLen) {
        if(s[l] == d[r]) {
            r++;
        }
        l++;
    }
    return r == dLen
}