查找常見字符Leetcode解決方案


難度級別 容易獎學金
經常問 土磚 亞馬遜 蘋果 彭博社 谷歌 Microsoft微軟 到到網 尤伯杯
排列 哈希

問題陳述

在這個問題上,我們得到了一個 排列 of 字符串。 我們需要打印數組中每個字符串中出現的所有字符的列表(包括重複項)。 也就是說,如果一個字符在每個字符串中出現2次,而不是3次,那麼我們需要在結果中將其重複2次。

請注意,字符串中的每個字符都是小寫英文字母,並且字符串的最大長度為100。

String_Array = {"bella" , "ciao" , "espanol"}
a
String_Array = {"qweerty" , "weerty" , "eerty"}
e e r t y

 

查找常見字符Leetcode解決方案

方法(哈希圖)

我們可以先使用一個哈希圖 最終計數 存儲在['a','z']中的字符數以存儲其字符 最低限度 存在於所有弦樂中。 例如,如果我們發現數組中的每個字符串中都有2個“ e”,則將其計數保持為2。為了實現這一點,我們將遍歷數組中的每個字符串並將其最小化。 最終計數 對於['a','z']中的每個字符。 最後,我們根據字符的最終計數將其壓入結果數組/列表中並返回它。

算法

  1. 初始化哈希圖 最終計數 存儲每個字符的最小外觀
  2. 對於每個小寫英文字母:
    • 設置他們的 最終計數 為100。
  3. 對於每個字符串 字 在給定的數組中:
    • 將每個字符的計數存儲在哈希圖中
    • 對於每個小寫英文字母 c:
      • 組: finalCount [c] = 分鐘 (finalCount [c],count [c])
  4. 初始化列表/數組 導致 存儲常用字符數組。
  5. 對於每個角色 在['a','z']範圍內:
    • 將其添加到列表的次數為 finalCount [E]
  6. 打印結果

查找公用字符Leetcode解決方案的實現

C ++程序

#include <bits/stdc++.h>
using namespace std;

vector <string> commonChars(vector <string> A)
{
    unordered_map <char , int> finalCount;

    for(char c = 'a' ; c <= 'z' ; ++c)
        finalCount[c] = 100;

    unordered_map <char , int> count;

    for(string &word : A)
    {
        count.clear();
        for(char c : word)
            count[c]++;

        for(char c = 'a' ; c <= 'z' ; ++c)
            finalCount[c] = min(finalCount[c] , count[c]);
    }

    vector <string> result;

    string temp;

    int times;
    for(char c = 'a' ; c <= 'z' ; ++c)
    {
        times = finalCount[c];
        temp = c;
        while(times > 0)
        {
            result.push_back(temp);
            --times;
        }
    }
    return result;
}

int main()
{
    vector <string> A = {"qweerty" , "weerty" , "eerty"};
    vector <string> result = commonChars(A);
    if(result.empty())
        cout << "No common characters\n";
    else
    {
        for(string &s : result)
            cout << s << " ";
    }

    return 0;
}

Java程序

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

class common_chars
{
    public static void main(String args[])
    {
        String[] A = {"qweerty" , "weerty" , "eerty"};
        List <String> result = commonChars(A);
        if(result.size() == 0)
            System.out.println("No common characters");
        else
        {
            for(String s : result)
                System.out.print(s + " ");
        }
    }

    static List <String> commonChars(String[] A)
    {
        HashMap <Character , Integer> finalCount = new HashMap<>();

        for(char c = 'a' ; c <= 'z' ; ++c)
            finalCount.put(c , 100);

        HashMap <Character , Integer> count = new HashMap<>();
        for(String word : A)
        {
            count.clear();
            for(char c : word.toCharArray())
                count.put(c , count.getOrDefault(c , 0) + 1);

            for(char c = 'a' ; c <= 'z' ; ++c)
                finalCount.put(c , Math.min(finalCount.get(c) , count.getOrDefault(c , 0)));
        }

        List <String> result = new ArrayList<>();

        int times;
        for(char c = 'a' ; c <= 'z' ; ++c)
        {
            times = finalCount.get(c);
            while(times > 0)
            {
                result.add(Character.toString(c));
                --times;
            }
        }
        return result;
    }
}
e e r t y

查找公共字符Leetcode解決方案的複雜性分析

時間複雜度

上) 因為我們對數組中的每個字符串進行了一次遍歷以更新字符計數。 N =數組中字符串長度的總和。

空間複雜度

O(1) 因為我們使用恆定的內存空間來存儲字符數。