सामान्य वर्ण लेटकोड समाधान खोजें


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना Uber
ऐरे hashing

समस्या का विवरण

इस समस्या में, हमें एक सूची दी गई है स्ट्रिंग। हमें उन पात्रों का पता लगाना होगा जो सभी तारों में सामान्य हैं। यदि एक चरित्र कई बार सभी तारों में मौजूद होता है, तो हमें चरित्र को कई बार आउटपुट करना होगा।
मान लीजिए, हमारे पास तार हैं
["बेला", "लेबल", "रोलर"]
हम देख सकते हैं कि, चरित्र 'ई' सभी तारों में एक बार मौजूद है, एल सभी तारों में दो बार मौजूद है। कोई और चरित्र आम नहीं है।
तो, हमारी आउटपुट सूची में, चरित्र 'ई' एक बार मौजूद होगा और चरित्र 'एल' दो बार मौजूद होगा।

उदाहरण

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

दृष्टिकोण

हम देख सकते हैं कि हमें यहाँ सभी स्ट्रिंग्स में वर्ण az की सामान्य आवृत्ति का पता लगाना है।
प्रत्येक स्ट्रिंग के लिए हम 26 आकार का एक काउंट सरणी बना सकते हैं, जिसमें अक्षर az की आवृत्ति होती है। इंडेक्स 0 में उस स्ट्रिंग में 'ए' की गिनती होगी और इंडेक्स 1 में 'बी' और इसी तरह की गिनती होगी।
अब प्रत्येक वर्ण से लेकर z तक, हमें न्यूनतम गणना का पता लगाना होगा जो ऊपर बनाई गई किसी भी सारणी में मौजूद हो सकती है। हम ऐसा कर रहे हैं, क्योंकि हम सभी तारों में एक चरित्र की न्यूनतम उपस्थिति में रुचि रखते हैं। दूसरे शब्दों में, हम केवल प्रत्येक स्ट्रिंग से सामान्य वर्ण ले रहे हैं।

 

सामान्य वर्ण लेटकोड समाधान खोजें

तो, हम सबसे पहले एक ans बनाएंगे सरणी 26 का आकार जो अधिकतम मूल्य पर सभी अनुक्रमित सेट कर रहा है।
फिर, हम बाएं से दाएं तारों के सरणी को पीछे छोड़ेंगे। प्रत्येक चरण में, हम वर्तमान स्ट्रिंग के लिए गिनती सरणी बनाएंगे। फिर हम वर्तमान बनाए गए एरे की एन्स एरे से तुलना करेंगे।
क्योंकि हम सभी में न्यूनतम रुचि रखते हैं, इस प्रकार ans सरणी के प्रत्येक सूचकांक को केवल तभी संशोधित किया जाएगा जब वर्तमान सरणी में मान उस सूचकांक पर ans सरणी के मान से छोटा हो।
यानी अगर ans [i]

हमने दी गई सूची के सभी तारों का पता लगाने के बाद, हम वर्णों की सूची बनाने के लिए अपने ans सरणी का उपयोग करेंगे। उत्तर सरणी में, इंडेक्स 0 का मान, वर्ण 'a' की गिनती दिखाता है, इंडेक्स 1 का मान इंडेक्स 'b' और इसी तरह का काउंट दिखाता है।
तो, इस तरह हम प्रत्येक वर्णों की गणना का उपयोग करके ए से लेकर जेड तक अपने आउटपुट एरे को बनाएंगे।

कार्यान्वयन

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

सामान्य वर्ण 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

कॉमन कैरेक्टर लेटकोड सॉल्यूशन के लिए जटिलता विश्लेषण

समय जटिलता

पर): जहां n सभी तारों की लंबाई का योग है।

अंतरिक्ष जटिलता 

ओ (1): दो सरणियों ans और अस्थायी, प्रत्येक आकार 26 का उपयोग किया जाता है। जो एक स्थिर आकार की मेमोरी के अलावा और कुछ नहीं है। इस प्रकार अंतरिक्ष जटिलता O (1) है।