[演算法題目] Generate Document

本題資訊

難度：easy
使用語言：C++
相關概念：String

題目敘述

You’re given a string of available characters and a string representing a document that you need to generate. Write a function that determines if you can generate the document using the available characters. If you can generate the document, your function should return true; otherwise, it should return false.

You’re only able to generate the document if the frequency of unique characters in the characters string is greater than or equal to the frequency of unique characters in the document string. For example, if you’re given characters = "abcabc" and document = "aabbccc" you cannot generate the document because you’re missing one c.

The document that you need to create may contain any characters, including special characters, capital letters, numbers, and spaces.

Input:

characters = "worldOhell o"
document = "hello wOrld"

Output:

true

Idea

這題雖然題目偏向字串處理，不過因為和字元計算相關（字元-字數對應），蠻經典的做法就是利用 map，實際上感覺是在考應用 map 的簡單概念。

我這裡先跑一輪所有的 characters，把出現的字母和次數紀錄在 chCount 內。再來就跑一輪 document，並且把對應到的字母數量減 1。這樣若有數量減少到小於 0，就表示當初 characters 內的字母沒有辦法生成 document。跑完後若都沒有小於 0 的狀況，就表示 characters 內的字數夠。

#include <unordered_map>
using namespace std;

bool generateDocument(string characters, string document) {
  unordered_map<char, int> chCount;

  for (auto ch : characters) {
    chCount[ch]++;
  }
  for (auto ch : document) {
    chCount[ch]--;
    if (chCount[ch] < 0)
      return false;
  }
  return true;
}

時間複雜度：\(O(n+m)\)，\(n\) 是 characters 長度，\(m\) 是 document 長度。
空間複雜度：\(O(k)\)，\(k\) 是 characters 內唯一字元的個數。