# 1160. Find Words That Can Be Formed by Characters

## 題目敘述

題目意思:
chars內英文必須可以組成words裡面的單詞，不需看順序
如範例
Input: words = ["cat","bt","hat","tree"], chars = "atach"
cat 有 at c
hat 有 at h
所以總共有 3+3 = 6
Output: 6

## 初步想法
### 第一次看到
想要統計chars哪個字符有幾次，比如 a:2 t:1 c:1 h:1
words陣列中內自一個個拉出來比較，cat中 c:1 a:1 t:1
當words內字符都有被chars包含，
則該字有符合，算入字數加總

## 解題

### 作法1 : array間比較

var countCharacters = function(words, chars) {
    let chars_keys = hashMap(chars)
    let ans = 0
    
    for(let i in words){
      let matchOrNot = 0
      let word_keys = hashMap(words[i])

      for(let prop in word_keys){
      //word_keys prop 必須在chars_keys 且兩數相減必須大於等於0
        if(chars_keys[prop] == undefined || chars_keys[prop] - word_keys[prop] < 0){
          matchOrNot = 1
          break
        }
      }
      if(matchOrNot == 0) ans += words[i].length
    }
    return ans
    
    
    // 將chars用 hash map 如 a:2 c:1 t:1 h:1，按照字母順序，以加速之後運行時間
    function hashMap(array){
      let keys ={}
      array = array.split('').sort().join('') 
      for(let i in array){
        if(keys[array[i]] == undefined){
          keys[array[i]] = 1
        }
        else keys[array[i]] += 1
      }
      return keys
    }
    
};

### 說明:

array = array.split('').sort().join('') 

將每一個字串預處理，如 chars = "atach"
* 字符取出
chars.split('') 得到 [ 'a', 't', 'a', 'c', 'h' ]
* 排序後
chars.split('').sort() 得到 [ 'a', 'a', 'c', 'h', 't' ]
* 去掉''
chars.split('').sort().join('') 得到 aacht

> 使用這個方式是為了之後遍歷時，可以比較快

if(chars_keys[prop] == undefined || chars_keys[prop] - word_keys[prop] < 0){
          matchOrNot = 1
          break
        }

* chars_keys[prop] == undefined
遍歷中，prop就是迴圈中array的key，所以此為判斷chars_keys中是否具有word_key，如果沒有就直接不符合

* chars_keys[prop] - word_keys[prop] < 0
判斷chars_keys中該key數量-word_keys中該key數量是否足夠，不足直接不符合

### 最終結果

###### tags: `Leetcode`