📂
LeetCode Note
  • Introduction
  • Tools
    • Clean Code
    • 英文小辭典
    • JS Reference
    • 常見 Edge Case
    • Array Method
    • Object Method
    • Function
    • Hashing
    • Prototype
    • 處理 Array 小撇步
    • String Method
    • Math / Date
    • loop
    • JSON.xx / localStorage
    • Date
    • Regex
    • Memorization
    • reduce condition
    • 命名
  • 筆記 Note
    • Promise
    • Walking the DOM
    • Element size and scrolling
    • CSS
  • Leetcode todo
    • ToDo
  • Array
    • # Select random poker without duplicates
    • # 最少替換達成不連續字串
    • # 724 Find Pivot Index
    • # 747. Largest Number At Least Twice of Others
    • # 01 getMaxProfit
    • # maxOfBiggestVal
    • # findSecondLargest
    • # 41 First Missing Positive
    • # 134 Gas Station (有圖)
    • # 202 Happy Number
    • # 344 Reverse String
    • # 412 Fizz Buzz
    • # 561 Array Partition I
    • # 804 Unique Morse Code Words
    • # 905 Sort Array By Parity
    • # 121. Best Time to Buy and Sell Stock.js
    • # 122 Best Time to Buy and Sell Stock II
    • # 189 Rotate Array
    • # 229 Majority Element II
    • # 268 Missing Number.
    • # 299 Bulls and Cows (有圖)
    • # 896 Monotonic Array
    • # 1002 Find Common Characters
    • # 1051 Height Checker
    • # 1185 Day of the Week
    • # 169 Majority Element
    • # 605. Can Place Flowers
    • # 350 Intersection of Two Arrays II (有圖)
    • # 482. License Key Formatting
  • Set / Map
    • # GetLengthOfLongestSubstring
    • #1 Two Sum
    • # 217 Contains Duplicate
    • # 1122 Relative Sort Array
    • # 1160 Find Words That Can Be Formed by Characters
    • #811 Subdomain Visit Count
    • # 349 Intersection of Two Arrays
    • # 819 Most Common Word
  • Two Pointer
    • #704. Binary Search
    • #26 Remove Duplicates from Sorted Array (有圖)
    • #27 Remove Element
    • # 66 Plus One
    • # 80 Remove Duplicates from Sorted Array II (有圖)
    • # 88 Merge Sorted Array (有圖)
    • # 125 Valid Palindrome
    • #167 Two Sum II - Input array is sorted (有圖)
    • # 283 Move Zeroes (有圖)
    • # 38 Count and Say
    • # 557. Reverse Words in a String III
    • #977 Squares of a Sorted Array
    • #209 Minimum Size Subarray Sum
  • String
    • # 13 Roman to Integer (有圖)
    • # 771 Jewels and Stones
    • # 937 Reorder Data in Log Files
    • # 929 Unique Email Addresses
    • # 1108 Defanging an IP Address
    • #14 Longest Common Prefix
    • # 387 First Unique Character in a String (有圖)
    • #193 Valid Phone Numbers
    • # 28 Implement strStr()
    • #383 Ransom Note
  • Stack
    • # 20 Valid Parentheses (有圖)
    • # 155 Min Stack
    • BF 165. remove characters
    • #1047 Remove All Adjacent Duplicates In String
  • Binary Search
    • # 1064 Fixed Point (有圖)
    • # 852 Peak Index in a Mountain Array
  • Recursion 遞迴
    • #2625. Flatten Deeply Nested Array
  • Math
    • # 7 Reverse Integer
    • # 9 Palindrome Number (有圖)
    • #53 Maximum Subarray (有圖)
    • # 1085 Sum of Digits in the Minimum Number.
    • # 136 Single Number
    • # 204 Count Primes (有圖)
    • #243 Shortest Word Distance
  • Dynamic Programing
    • # 322 Coin Change
    • # 509 Fibonacci Number (有圖)
    • # 70 Climbing Stairs
    • # 198 House Robber
    • # 168. Excel Sheet Column Title
  • Others
    • # 205. Isomorphic Strings
    • Implement js Array method
    • Flatten Array/Object
  • Matrix
    • 867. Transpose Matrix
  • Queue
    • DOM tree with queue
  • 排序
    • Different Sort
Powered by GitBook
On this page

Was this helpful?

  1. Set / Map

# 1160 Find Words That Can Be Formed by Characters

Previous# 1122 Relative Sort ArrayNext#811 Subdomain Visit Count

Last updated 5 years ago

Was this helpful?

You are given an array of strings words and a string chars.

A string is good if it can be formed by characters from chars (each character can only be used once).

Return the sum of lengths of all good strings in words.

input: 一字串陣列 words 跟一個字串 chars
output: 回傳 words 全部符合 chars 的字串長度
Example 1:

Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: 
The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

Example 2:

Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr"
Output: 10
Explanation: 
The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.
 

Note:

1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100
All strings contain lowercase English letters only.


/**
 * @param {string[]} words
 * @param {string} chars
 * @return {number}
 */
var countCharacters = function(words, chars) {}

怎麼解

一個字串只能被用一次,我想到會先把 chars 存進 map 裡,然後 words 再去看有沒有符合

var countCharacters = function(words, chars) {
    // 統計 chars 字母出現次數
    let myMap= new Map();
    for(let i = 0; i< chars.length; i++){
      if(myMap.has(chars[i])){
        myMap.set(chars[i], myMap.get(chars[i]) + 1)
      }else{
        myMap.set(chars[i], 1)
      }
    }


    // 統計最後結果數字
    let totalCount = 0

    // 一個一個比對
    words.map(word => {

      let allPass = true

      // 統計 word 各個字出現數量
      let wordMap = new Map();
      for (let i = 0; i < word.length; i++) {
        if(myMap.has(word[i])){
          
          let count = !wordMap.get(word[i]) ? 1 : wordMap.get(word[i]) + 1;
          wordMap.set(word[i], count)
        }else{
          allPass = false  
          break;
        }
      }
      let lengthPass = true;
      
      // 比對出現次數有沒有大於 chars,大於的話就不過
      if(allPass){
        let countLen = 0
        wordMap.forEach((value, index) => {
            countLen += value;
            if(value > myMap.get(index)){
                lengthPass = false
            }   
        })

        if( lengthPass){
            totalCount += countLen;
        }
      }
    //  
      
      
     
    })
    return totalCount;
};

console.log(countCharacters(["catc","bt","hat","tree"],'atach'))
//faster than 84.68% of JavaScript online submissions
LeetCode