Поиск общих символов Решение Leetcode


Сложный уровень Легко
Часто спрашивают в Амазонка Uber
массив хеширования

Постановка задачи

В этой задаче нам дается список строка. Мы должны найти символы, которые являются общими для всех строк. Если символ присутствует во всех строках несколько раз, мы должны вывести этот символ несколько раз.
Допустим, у нас есть массив строк
[«Белла», «этикетка», «ролик»]
Мы видим, что символ 'e' присутствует один раз во всех строках, а l присутствует дважды во всех строках. Никакой другой персонаж не встречается.
Итак, в нашем выходном списке символ «e» будет присутствовать один раз, а символ «l» будет присутствовать дважды.

Пример

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

Подход

Мы видим, что здесь нам нужно узнать общую частоту символов az во всех строках.
Для каждой строки мы можем создать массив счетчиков размером 26, который имеет частоту символов az. индекс 0 будет иметь счетчик «a» в этой строке, а индекс 1 будет иметь счетчик «b» и так далее.
Теперь для каждого символа от a до z мы должны определить минимальное количество, которое может присутствовать в любом из массивов, созданных выше. Мы делаем это, потому что заинтересованы в минимальном наличии символа во всех строках. Другими словами, мы берем только общие символы из каждой строки.

 

Поиск общих символов Решение Leetcode

Итак, сначала создадим ответ массив размера 26, у которого все индексы установлены на максимальное значение.
Затем мы пройдем по массиву строк слева направо. На каждом шаге мы будем создавать массив count для текущей строки. Затем мы сравним текущий созданный массив с массивом ans.
Поскольку нас интересует минимум всего, каждый индекс массива ans будет изменен только в том случае, если значение в текущем массиве меньше, чем значение массива ans в этом индексе.
т.е. если ans [i]

После того, как мы пройдем все строки данного списка, мы будем использовать наш массив ans для создания списка символов. В массиве ответов значение в индексе 0 показывает количество символов «a», значение в индексе 1 показывает количество символов в индексе «b» и так далее.
Таким образом, мы сделаем наш выходной массив символов, используя количество каждого символа от a до z.

Реализация

Программа на C ++ для поиска общих символов Leetcode Solution

#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 Solution

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 - сумма длин всех строк.

Космическая сложность 

О (1): Используются два массива ans и temp, каждый размером 26. которая представляет собой не что иное, как память постоянного размера. Таким образом, сложность пространства O (1).