查找可以由字符Leetcode解决方案形成的单词


难度级别 易得奖学金
经常问 亚马逊
排列 哈希

问题陈述

在“查找可以由字符形成的单词”问题中,我们获得了由小写英文字母组成的字符串数组 (字) 的网络 绳子 由一组字符组成 (字符).

我们的任务是检查数组中的每个字符串是否可以使用chars字符形成(我们只能使用一次char每个字符)。 最后,我们需要返回所有可以使用chars字符串字符形成的字符串长度的总和。

使用案列

words = ["hello","world","tutorialcup"], chars = "welldonehoneyr"
10

说明:

查找可以由字符Leetcode解决方案形成的单词

在此示例中,我们可以使用chars字符串的字符来构成hello和world。 因此,hello和world的总长度为5 + 5 = 10。

查找可通过字符Leetcode解决方案形成的单词的方法

为了解决这个问题,我们将使用一个频率数组,该数组将存储字符串中存在的字符数。 我们将按照以下步骤解决问题:

  1. 创建一个频率数组并存储字符字符串的频率。
  2. 现在,一一检查单词数组的每个字符串。
    1. 创建频率阵列的副本。
    2. 现在检查所选字符串的每个字符。 如果频率数组中某个字符的频率小于1,则我们无法使用chars字符串的字符形成选定的字符串,否则将字符频率降低1。
    3. 如果可以使用chars字符串的字符构造字符串,则将所选字符串的长度添加到结果中。
  3. 返回结果的值。

实施

用于查找可以由字符形成的单词的C ++代码

#include <bits/stdc++.h> 
using namespace std; 
int countCharacters(vector<string>& words, string chars) {
  vector<int> cnt(26);
  int res = 0;
  for (auto ch : chars) ++cnt[ch - 'a'];
  for (auto w : words) {
    vector<int> cnt1 = cnt;
    bool match = true;
    for (auto ch : w) {
      if (--cnt1[ch - 'a'] < 0) {
        match = false;
        break;
      }
    }
    if (match) res += w.size();
  }
  return res;
}

int main() 
{ 
    vector<string> words {"hello","world","tutorialcup"};
    string ch="welldonehoneyr";
    int ans=countCharacters(words,ch); 
    cout<<ans<<endl;
    return 0;
}
10

用于查找可以由字符形成的单词的Java代码

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
public static int countCharacters(String[] words, String chars) {
        int[] count = new int[26];
        int res = 0;
        
        for (char ch : chars.toCharArray()) {
            count[ch - 'a']++;
        }
        
        for (String word : words) {
            int[] temp = count.clone();
            boolean match = true;
            
            for (char ch : word.toCharArray()) {
                if (--temp[ch - 'a'] < 0) {
                    match = false;
                    break;
                }
            }
            
            if (match) {
                res += word.length();
            }
        }
        
        return res;
    }
  public static void main(String[] args) {
        String[] words={"hello","world","tutorialcup"};
        String ch="welldonehoneyr";
        int ans=countCharacters(words,ch); 
        System.out.println(ans);
  }
}
10

字符Leetcode解决方案可以形成的查找词的复杂性分析

时间复杂度

上面代码的时间复杂度是 O(n * m) 因为我们正在遍历所有单词的每个字符。 这里n是给定数组的长度,m是给定数组的字符串的最大长度。

空间复杂度

上面代码的空间复杂度是 O(1) 因为我们只使用一个变量来存储答案。

參考資料