일반적인 문자 Leetcode 솔루션 찾기

난이도 쉽게
자주 묻는 질문 아마존 동네 짱
알고리즘 배열 코딩 해싱 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 28

문제 정책

이 문제에서 우리는 . 우리는 모든 문자열에서 공통적 인 문자를 찾아야합니다. 한 문자가 모든 문자열에 여러 번 존재하는 경우 문자를 여러 번 출력해야합니다.
문자열 배열이 있다고 가정 해 보겠습니다.
[ "bella", "label", "roller"]
문자 'e'는 모든 문자열에 한 번 존재하고 l은 모든 문자열에 두 번 존재한다는 것을 알 수 있습니다. 다른 캐릭터는 일반적이지 않습니다.
따라서 출력 목록에서 문자 'e'는 한 번, 문자 'l'은 두 번 나타납니다.

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

접근

여기서 모든 문자열에서 문자 az의 공통 빈도를 찾아야한다는 것을 알 수 있습니다.
모든 문자열에 대해 문자 빈도가 az 인 크기 26의 개수 배열을 만들 수 있습니다. 인덱스 0은 해당 문자열에서 'a'의 개수를 가지며 인덱스 1에는 'b'의 개수가 있습니다.
이제 a에서 z까지의 각 문자에 대해 위에서 만든 배열에 존재할 수있는 최소 개수를 찾아야합니다. 모든 문자열에서 문자의 최소 존재에 관심이 있기 때문에이 작업을 수행합니다. 즉, 각 문자열에서 공통 문자 만 가져옵니다.

 

일반적인 문자 Leetcode 솔루션 찾기

그래서 우리는 먼저 ans를 만들 것입니다 정렬 모든 인덱스가 최대 값으로 설정된 크기 26입니다.
그런 다음 왼쪽에서 오른쪽으로 문자열 배열을 탐색합니다. 각 단계에서 현재 문자열에 대한 개수 배열을 만듭니다. 그런 다음 현재 생성 된 배열을 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) : 두 개의 배열 ans 및 temp, 각각 크기 26이 사용됩니다. 이것은 일정한 크기의 메모리 일뿐입니다. 따라서 공간 복잡도는 O (1)입니다.

코멘트를 남겨

Translate »
1