采用哈希表统计。


inline bool is_digit(char c) { return '0' <= c && c <= '9'; }
inline char to_lower(char c) {
  if ('A' <= c && c <= 'Z') {
    return c + 'a' - 'A';
  }
  return c;
}

class Solution {
public:
  string shortestCompletingWord(string licensePlate, vector<string> &words) {
    map<char, int> target;
    // statistic
    auto len = licensePlate.length();
    for (size_t i = 0; i < len; i++) {
      auto ch = licensePlate[i];
      if (ch == ' ' || is_digit(ch)) {
        continue;
      }
      ch = to_lower(ch);
      auto itr = target.find(ch);
      if (itr == target.end()) {
        target[ch] = 1;
      } else {
        target[ch]++;
      }
    }
    // verification
    int minlen = INT_MAX;
    string minstr;
    auto count = words.size();
    for (size_t i = 0; i < count; i++) {
      auto _m(target);
      auto len = words[i].length();
      for (size_t j = 0; j < len; j++) {
        auto itr = _m.find(words[i][j]);
        if (itr == _m.end()) {
          continue;
        }
        _m[words[i][j]]--;
      }
      // is all zero?
      bool allzero = true;
      for (auto &&i : _m) {
        if (i.second > 0) {
          allzero = false;
          break;
        }
      }
      if (!allzero) {
        continue;
      }
      if (len < minlen) {
        minlen = len;
        minstr = words[i];
      }
    }
    return minstr;
  }
};

改成数组性能可以提高一点:

class Solution {
public:
  string shortestCompletingWord(string licensePlate, vector<string> &words) {
    int target[26];
    memset(target, 0, 26 * sizeof(int));
    // statistic
    auto len = licensePlate.length();
    for (size_t i = 0; i < len; i++) {
      auto ch = licensePlate[i];
      if (ch == ' ' || is_digit(ch)) {
        continue;
      }
      ch = to_lower(ch);
      target[ch - 'a']++;
    }
    // verification
    int minlen = INT_MAX;
    string *minstr;
    auto count = words.size();
    for (size_t i = 0; i < count; i++) {
      int _m[26];
      memcpy(_m, target, 26 * sizeof(int));
      auto len = words[i].length();
      for (size_t j = 0; j < len; j++) {
        _m[words[i][j] - 'a']--;
      }
      // is all <= 0?
      bool noPositiveNumber = true;
      for (int i = 0; i < 26; i++) {
        if (_m[i] > 0) {
          noPositiveNumber = false;
          break;
        }
      }

      if (!noPositiveNumber) {
        continue;
      }
      if (len < minlen) {
        minlen = len;
        minstr = &words[i];
      }
    }
    return *minstr;
  }
};