查找常见字符Leetcode解决方案  


难度级别 易得奖学金
经常问 亚马逊 尤伯杯
算法 排列 编码 哈希 访谈 面试准备 力码 力码解决方案

问题陈述  

在这个问题上,我们得到一个清单 绳子。 我们必须找出所有字符串中共有的字符。 如果一个字符多次出现在所有字符串中,那么我们必须多次输出该字符。
假设我们有一个字符串数组
[“ bella”,“ label”,“ roller”]
我们可以看到,字符“ e”在所有字符串中都出现一次,l在所有字符串中都出现两次。 没有其他字符是常见的。
因此,在我们的输出列表中,字符“ e”将出现一次,字符“ l”将出现两次。

使用案列

["bella","label","roller"]
["e","l","l"]
["cool","lock","cook"]
["c","o"]

途径  

我们可以看到,我们必须在这里找出所有字符串中字符az的常见频率。
对于每个字符串,我们都可以创建一个大小为26的计数数组,该数组的字符频率为az。 索引0在该字符串中的计数为“ a”,而索引1的计数为“ b”,依此类推。
现在,对于从a到z的每个字符,我们必须找出上面创建的任何数组中可能存在的最小计数。 之所以这样做,是因为我们对所有字符串中字符的最少存在感兴趣。 换句话说,我们仅从每个字符串中提取公共字符。

参见
Rook Leetcode解决方案的可用捕获

 

查找常见字符Leetcode解决方案Pin

因此,我们将首先创建一个ans 排列 大小为26的索引,所有索引均设置为最大值。
然后,我们将从左到右遍历字符串数组。 在每个步骤中,我们将为当前字符串创建count数组。 然后,我们将当前创建的数组与ans数组进行比较。
因为我们对所有的最小值感兴趣,因此,仅当当前数组中的值小于该索引处的ans数组的值时,才会修改ans数组的每个索引。
即如果ans [i]

遍历给定列表的所有字符串后,我们将使用ans数组创建字符列表。 在答案数组中,索引0的值显示字符'a'的计数,索引1的值显示索引'b'的计数,依此类推。
因此,通过这种方式,我们将通过使用从a到z的每个字符的计数来构成我们的字符输出数组。

实施   

查找公用字符Leetcode解决方案的C ++程序

#include <iostream>
#include <vector>
using namespace std;
vector<string> commonChars(vector<string>& A) {
        int ans[26];
        int temp[26];
        fill(ans,ans+26,100);
        for(string str:A){
            fill(temp, temp+26,0);
            for(int i=0;i<str.size();i++){
                temp[str[i]-'a']++;
            }
            for(int i=0;i<26;i++){
                ans[i]=min(ans[i],temp[i]);
            }
        }
        vector<string>ansChars;
        for(int i=0;i<26;i++){
            for(int j=0;j<ans[i];j++){
                char ch=((char)(i+'a'));
                string s(1, ch); //convert char ch to string s
                ansChars.push_back(s);
            }
        }
        return ansChars;
    }
int main()
{
    vector<string>A{"bella","label","roller"};
    vector<string>ans = commonChars(A);
    for(string str:ans){
        cout<<str<<" ";
    }
    cout<<endl;
}
e l l

查找公用字符Leetcode解决方案的Java程序

import java.util.*;
import java.lang.*;

class Solution
{  
    public static void main(String args[])
    {
        String[]A={"bella","label","roller"};
        List<String>ans=commonChars(A);
        for(String str:ans){
            System.out.print(str+" ");
        }
        System.out.println();
    }
    public static List<String> commonChars(String[] A) {
        int[]ans=new int[26];
        int[]temp=new int[26];
        Arrays.fill(ans,Integer.MAX_VALUE);
        for(String str:A){
            Arrays.fill(temp,0);
            for(int i=0;i<str.length();i++){
                temp[str.charAt(i)-'a']++;
            }
            for(int i=0;i<26;i++){
                ans[i]=Math.min(ans[i],temp[i]);
            }
        }
        List<String>ansChars=new ArrayList<String>();
        for(int i=0;i<ans.length;i++){
            for(int j=0;j<ans[i];j++){
                ansChars.add((char)(i+'a')+"");
            }
        }
        return ansChars;
    }
}
e l l

查找常见字符Leetcode解决方案的复杂性分析  

时间复杂度

上): 其中n是所有字符串的长度之和。

参见
金矿问题

空间复杂度 

O(1): 分别使用大小为26的两个数组ans和temp。 这不过是恒定大小的内存。 因此,空间复杂度为O(1)。

1