LeetCode上猜字謎，元宵節(jié)和猜字謎更配哦，困難難度，記錄下解題思路

會傳入words和puzzle兩個數(shù)組，需要滿足以下兩個條件：

1. 當前元素中包含puzzle中元素的第一個字母
2. words元素的每一個字母在puzzle中都能找到

例如words中aaa和puzzle中aboveyz就滿足，循環(huán)的過程是每次取puzzle中的一個元素，然后循環(huán)整個words內(nèi)的元素，記錄下滿足上面兩個條件的元素個數(shù)，遍歷完所有puzzle元素后組成的數(shù)組就是結果。

如果只是用直接方法來，在最后一個案例就會超時

var findNumOfValidWords = function(words, puzzles) {
  let mapArr = []
  let wordsLength = words.length
  let puzzelsLength = puzzles.length
  // 返回結果
  let res = []
  // 遍歷words來構建map
  for(let i = 0; i < words.length;i++) {
    let map = new Map()
    for(let j = 0; j < words[i].length;j++) {
      if(!map.has(words[i][j])) map.set((words[i][j]),true)
    }
    mapArr.push(map)
  }
  // 遍歷puzzles內(nèi)的每個元素來完成條件判斷
  for(let i = 0; i<puzzelsLength; i++) {
    let p = puzzles[i]
    let first = p.substring(0,1)
    // 當前puzzle滿足條件的元素
    let w = 0
    // 遍歷整個mapArr
    for(let j = 0;j<wordsLength;j++) {
      let flag = true;
      // 2. p內(nèi)有當前map中的所有元素
      mapArr[j].forEach((x,i) => {
        if(p.indexOf(i) === -1) flag = false
      })
      // 1. 能夠找到當前p的第一個元素
      // 如果滿足上面兩個條件就是這個元素滿足條件
      if(mapArr[j].has(first) && flag) w++
    }
    res.push(w)
  }
  return res
};

如果將一個單詞轉(zhuǎn)換為二進制狀態(tài)？

JavaScript對于字符串方法有一個charCodeAt方法，能夠獲取字符串對應位置Unicode編碼值，將這個獲取的值，已知所有的元素都是小寫字母，小寫字母a對應的Unicode編碼值為97,用對應字符的編碼 - 97即為這個字母在字母表的位置，之后可以對應到二進制數(shù)中。

function trans (w) {
  // w是傳入的字符串
  // 返回的二進制結果
  let res = 0
  // 遍歷整個字符串
  for(let i = 0; i < w.length; i++) {
    // 先查每個字符對應的Unicode編碼
    let num = w[i].charCodeAt(0) - 97
    // 用位移的方法獲取2進制方法，右移一位
    let s = 1 << num
    // 通過或的方式實現(xiàn)2進制加法
    res = res | s
  }
  return res
}

這里面用到了一個位運算（<<）和或運算（|），這個位運算可以看JavaScript中 num >>> 0 發(fā)生了什么，或運算遵守以下規(guī)則1|1=1、1|0=1、0|1=1、0|0=0
假設現(xiàn)在傳入的字符串是abc
第一次獲取a的Unicode編碼為0，1<<0代表0向左移動一位，此時移動一位之后為1
與0進行或運算，最后得1
第二次獲取b的Unicode編碼為1，1<<1代表1向左移動一位，得到的2進制數(shù)為10，與1進行或運算可得11
第二次獲取c的Unicode編碼為2，1<<2代表10向左移動一位，得到的2進制數(shù)為100，與11進行或運算可得111
所以最后可得的結果是111，對應的十進制為7,

對比puzzle和word

將puzzle和word都轉(zhuǎn)換為二進制之后，需要對比

1. word內(nèi)有puzzle的首字母
2. word內(nèi)的所有字母都會存在于puzzle內(nèi)

接下來的兩點參考的LeetCode上大神的題解「手畫圖解」巧用位運算，思路解析 | leetcode 1178 猜字謎，下面是我自己的理解：

對于首字母存在的情況

將puzzle的首字母的二進制數(shù)，與word元素的二進制數(shù)進行與運算，如果不等于0，那么就表示當前word元素中有這個字母

例如abc的二進制轉(zhuǎn)換為111，puzzle = ca首字母為c轉(zhuǎn)換為二進制為100，111 & 100可得100，所以能夠表示有這個首字母

判斷所有字母都存在于puzzle內(nèi)
這里轉(zhuǎn)換為求puzzle的子集，如果某個子集能夠?qū)?code>word中的某個元素，那么就把這個元素的出現(xiàn)次數(shù)記錄下來。
那么問題就能轉(zhuǎn)換為如何求子集的問題了，參考上面大神的思路，十分巧妙。
新的子集 = （上次的二進制數(shù) - 1） & 最初的二進制數(shù)

假設puzzle = ca轉(zhuǎn)換為101，明顯可以看出ca的子集可以是[ca,c,a]排除0（空子集的情況）
（101 - 1）& 101 => 100 &101 => 100 => c
（100 - 1）& 101 => 011 &101 => 001 => a
（001 - 1）& 101 => 000 &101 => 000 => 空子集，此情況排除
所以總結總結下來可以得出以下代碼

var findNumOfValidWords = function(words, puzzles) {
  let mapArr = new Map()
  let wordsLength = words.length
  let puzzlesLength = puzzles.length
  // 返回結果,填充0，如果沒有結果那么直接就是0無需更多操作
  let res = Array(puzzlesLength).fill(0)
  // 遍歷words來構建map
  for(let i = 0; i < words.length;i++) {
    // 將這個元素轉(zhuǎn)換為二進制并且保存在map中
    let num = trans(words[i])
    if(mapArr.has(num)) {
      // 如果Map中之前出現(xiàn)過這個相同的字符串，就次數(shù)+1
      mapArr.set(num,mapArr.get(num) + 1)
    } else {
      // 如果沒出現(xiàn)過就設為1
      mapArr.set(num,1)
    }
  }
  console.log(mapArr);
  // 遍歷puzzles內(nèi)的每個元素來完成條件判斷
  for(let i = 0; i<puzzlesLength; i++) {
    // puzzles對應元素的二進制表現(xiàn)
    let p = trans(puzzles[i])
    let first = trans(puzzles[i][0])
    // 當前puzzle滿足條件的元素
    let w = p
    // 遍歷整個mapArr
    while (w > 0) {
      // 判斷首字母存在，且子數(shù)組位于map中
      if ((w & first) != 0 && mapArr.get(w) > 0) {
          res[i] += mapArr.get(w)
      }
      //生成一個新的子集合
      w = (w - 1) & p;
    }
  }
  return res
};

function trans (w) {
  // w是傳入的字符串
  // 返回的二進制結果
  let res = 0
  // 遍歷整個字符串
  for(let i = 0; i < w.length; i++) {
    // 先查每個字符對應的Unicode編碼
    let num = w[i].charCodeAt(0) - 97
    // 用位移的方法獲取2進制方法，右移一位
    let s = 1 << num
    // 通過或的方式實現(xiàn)2進制加法
    res = res | s
  }
  return res
}