Знайдзіце рашэнне агульных знакаў Leetcode


Узровень складанасці Лёгка
Часта пытаюцца ў амазонка Uber
масіў хэшавання

Пастаноўка праблемы

У гэтай праблеме мы атрымалі спіс радок. Мы павінны высветліць сімвалы, якія распаўсюджаны ва ўсіх струнах. Калі сімвал прысутнічае ва ўсіх радках некалькі разоў, нам трэба выводзіць сімвал некалькі разоў.
Дапусцім, у нас масіў радкоў
["Bella", "label", "roller"]
Мы бачым, што сімвал "е" прысутнічае адзін раз ва ўсіх радках, l - два разы ва ўсіх радках. Ні адзін іншы персанаж не сустракаецца.
Такім чынам, у нашым спісе вынікаў сімвал "е" будзе прысутнічаць адзін раз, а сімвал "л" будзе прысутнічаць двойчы.

Прыклад

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

Падыход

Мы бачым, што нам трэба высветліць агульную частату сімвалаў az ва ўсіх радках.
Для кожнай радкі мы можам стварыць масіў падліку памерам 26, які мае частату сімвалаў az. індэкс 0 будзе мець лік "a" у гэтым радку, а індэкс 1 - "b" і гэтак далей.
Цяпер для кожнага сімвала ад a да z мы павінны высветліць мінімальны лік, які можа прысутнічаць у любым з масіваў, створаных вышэй. Мы робім гэта, таму што мы зацікаўлены ў мінімальнай прысутнасці персанажа ва ўсіх радках. Іншымі словамі, мы бярэм толькі агульныя сімвалы з кожнай радкі.

 

Знайдзіце рашэнне агульных знакаў Leetcode

Такім чынам, мы спачатку створым анс масіў памерам 26, у якім усе індэксы ўстаноўлены на максімальнае значэнне.
Затым мы пройдзем масіў радкоў злева направа. На кожным этапе мы ствараем масіў падліку для бягучай радкі. Тады мы параўнаем створаны масіў з масівам ans.
Паколькі нас цікавіць мінімум усіх, такім чынам, кожны індэкс масіва ans будзе зменены толькі ў тым выпадку, калі значэнне ў бягучым масіве менш, чым значэнне масіва ans у гэтым індэксе.
г.зн. калі ans [i]

Пасля таго, як мы пройдзем усе радкі дадзенага спісу, мы будзем выкарыстоўваць наш масіў ans для стварэння спіса сімвалаў. У масіве адказаў значэнне ў індэксе 0 паказвае колькасць сімвала "a", значэнне ў індэксе 1 паказвае колькасць індэкса "b" і гэтак далей.
Такім чынам, такім чынам мы зробім наш выходны масіў сімвалаў, выкарыстоўваючы колькасць кожнага сімвала ад a да z.

Рэалізацыя

Праграма C ++ для пошуку агульнапрынятых сімвалаў рашэння Leetcode

#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

Праграма Java для пошуку агульнапрынятых сімвалаў рашэння Leetcode

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

Складанасць часу

O (n): дзе n - сума даўжыні ўсіх радкоў.

Касмічная складанасць 

O (1): выкарыстоўваюцца два масівы ans і temp, кожны памерам 26. што не што іншае, як памяць пастаяннага памеру. Такім чынам, касмічная складанасць складае O (1).