1160. 拼写单词 - countCharacters

[snow-swallow]

思路checkpoints:

1. 算法比较傻，一次次循环。。
2. perf optimize: 直接用len 放入loop 里去累加（代替results，因为计算len 还得遍历一次results）
3. perf optimize: 遍历单个word 验证是否有重复值时，采取验过即抹除index 对应的char，减少后续遍历的长度

/**
 * @param {string[]} words
 * @param {string} chars
 * @return {number}
 */
var countCharacters = function(words, chars) {
    let count = 0;
    let len = 0;
    // let results = [];
    let index = 0;
    let bk;
    for (let i = 0; i < words.length; i ++) {
        bk = chars;
        count = words[i].split('').filter(item => { 
            index = bk.indexOf(item) 
            if (index > -1) {
                bk = index == 0 ? bk.substr(1) : bk.substring(0, index) + bk.substr(index + 1);
                // bk = bk.replaceCharAt(index, '');
                return false; // hit
            } else {
                return true; // no hit
            }
        }).length;
        if (count == 0) { // all char hits
            // results.push(words[i]);
            len += words[i].length;
        }
    }
    // console.log(results);
    return len;
};

测试用例

Input:
["cat","bt","hat","tree"]
"atach"

Expected output: 
6
----
Input:
["dyiclysmffuhibgfvapygkorkqllqlvokosagyelotobicwcmebnpznjbirzrzsrtzjxhsfpiwyfhzyonmuabtlwin","ndqeyhhcquplmznwslewjzuyfgklssvkqxmqjpwhrshycmvrb","ulrrbpspyudncdlbkxkrqpivfftrggemkpyjl","boygirdlggnh","xmqohbyqwagkjzpyawsydmdaattthmuvjbzwpyopyafphx","nulvimegcsiwvhwuiyednoxpugfeimnnyeoczuzxgxbqjvegcxeqnjbwnbvowastqhojepisusvsidhqmszbrnynkyop","hiefuovybkpgzygprmndrkyspoiyapdwkxebgsmodhzpx","juldqdzeskpffaoqcyyxiqqowsalqumddcufhouhrskozhlmobiwzxnhdkidr","lnnvsdcrvzfmrvurucrzlfyigcycffpiuoo","oxgaskztzroxuntiwlfyufddl","tfspedteabxatkaypitjfkhkkigdwdkctqbczcugripkgcyfezpuklfqfcsccboarbfbjfrkxp","qnagrpfzlyrouolqquytwnwnsqnmuzphne","eeilfdaookieawrrbvtnqfzcricvhpiv","sisvsjzyrbdsjcwwygdnxcjhzhsxhpceqz","yhouqhjevqxtecomahbwoptzlkyvjexhzcbccusbjjdgcfzlkoqwiwue","hwxxighzvceaplsycajkhynkhzkwkouszwaiuzqcleyflqrxgjsvlegvupzqijbornbfwpefhxekgpuvgiyeudhncv","cpwcjwgbcquirnsazumgjjcltitmeyfaudbnbqhflvecjsupjmgwfbjo","teyygdmmyadppuopvqdodaczob","qaeowuwqsqffvibrtxnjnzvzuuonrkwpysyxvkijemmpdmtnqxwekbpfzs","qqxpxpmemkldghbmbyxpkwgkaykaerhmwwjonrhcsubchs"]
"usdruypficfbpfbivlrhutcgvyjenlxzeovdyjtgvvfdjzcmikjraspdfp"

Expected output: 
0

https://leetcode-cn.com/problems/find-words-that-can-be-formed-by-characters/

[snow-swallow]

顺便温习以下JS 原型链的使用

String.prototype.replaceCharAt = function(n,c){
  return this.substr(0, n)+ c + this.substr(n+1,this.length-1-n);
}

[snow-swallow]

update 下几种replace 部分的效率，以下几种性能递减：

1. bk = index == 0 ? bk.substr(1) : bk.substring(0, index) + bk.substr(index + 1);
2. bk = bk.replace(item, '');
3. bk = bk.replaceCharAt(index, '');

Comment: JS 的replace 性能随着字符串长度增加就变差了，String.prototype.replace 语法是: str.replace(regexp|substr, newSubStr|function). 具体没看清什么环节性能变差的，估计是每次是根据正则去匹配以及每次都生成一个新的string 对象，cost 变大

https://blog.csdn.net/yuhk231/article/details/88528839

[snow-swallow]

另一种解题思路是哈希表，用ES6 的map: get, set, has 函数

https://leetcode-cn.com/problems/find-words-that-can-be-formed-by-characters/solution/mei-ri-yi-ti-ep16-cnt-chars-pin-xie-dan-ci-javascr/