Word Pattern LeetCode Həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon alma Capital One Dropbox Facebook GoDaddy microsoft Über
BoltBaxılıb 31

Problem bəyanat

Word Pattern LeetCode Həlli – Bizə 2 sətir verilir – “s” və “naxış”, nümunənin s-dən sonra olub olmadığını tapmaq lazımdır. Burada izləmək tam uyğunluq deməkdir. Daha rəsmi desək, hər bir nümunə[i] üçün yalnız bir s[i] olmalıdır və əksinə, yəni nümunədəki hərf ilə s-də boş olmayan söz arasında bijection var.

Nümunələr və izahat

Misal 1:

Input: pattern = "abba", s = "dog cat cat dog"
Output: true
Explanation:
a -> dog
b -> cat

Misal 2:
Input: pattern = "abba", s = "dog cat cat fish"
Output: false
Explanation:
a -> dog
b -> cat
pattern[3] = a which corresponds to s[0], dog defined earlier, but s[3] has no dog

Misal 3:
Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false
Explanation:
a -> dog
Two different a are defined, i.e. dog and cat

Yanaşma

Biz s hərflərindəki sözləri nümunədəki uyğun hərflərlə əlaqələndirəcəyik. Əgər naxış[i] artıq mövcuddursa, s[i]-nin nümunə[i] ilə bərabər olub olmadığını yoxlayın. Nümunə[i] və “s”dəki dünyaları xəritələşdirmək üçün hasshmaplardan istifadə edək.

Sözlər tək bir s sətri ilə verildiyi üçün, asan həyata keçirmək üçün bütün sözləri saxlamaq üçün başqa bir sıra sətirlər təyin edə bilərik. s sətrini təkrarlayın, boşluq varsa, sözü sətir massivimizə itələyin.

Kodu

Word Pattern LeetCode üçün C++ kodu

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        map<char,string> cnt;
        vector<string> words;
        string t="";
        for(int i=0; i<=s.size(); i++) {
            if(s[i] == '\0') {
                words.push_back(t);
                break;
            }
            else if(s[i] == ' ') {
                words.push_back(t);
                t="";
            }
            else t+=s[i];
            
        }
        
        if(words.size() != pattern.size()) return 0;
        
        map<string, int> vis; // vis = visited
        for(int i=0; i<pattern.size(); i++) {
            // pattern already exists
            if(cnt.find(pattern[i]) != cnt.end()) {
                if(cnt[pattern[i]] != words[i]) return 0;
                
                
            }
            else {
                cnt[pattern[i]] =  words[i];
                if(vis[words[i]]) return 0;
                vis[words[i]] = 1;
            }
        }
        return 1;
    }
};

Word Pattern LeetCode üçün Java Kodu

class Solution {
    public boolean wordPattern(String pattern, String s) {
        Map<Character,String> m=new HashMap<>();
        String words[]=s.split(" ");
        
        if(pattern.length()!=words.length) return false;
        
        int n = words.length;
        for(int i=0;i<n;i++){
            
            char c= pattern.charAt(i);
            
            if(m.containsKey(c)){
                if(!words[i].equals(m.get(c))) return false;
            }
            else{
                if(m.containsValue(words[i])){
                    return false;
                }
                m.put(c, words[i]);
            }
        }
        return true;
    }
}

Word Pattern LeetCode Həlli üçün Mürəkkəblik Təhlili

  • Zaman mürəkkəbliyi: O(N)
  • Kosmik mürəkkəblik: O(M)
    • M təmsil edir unikal sayı s-dəki sözlər. Baxmayaraq ki, 2 həşməp var, ən çoxu 26 düymə ola bilər, ona görə də xəritənin məkan mürəkkəbliyi sabitdir.

Referans: https://en.wikipedia.org/wiki/Pattern_matching

Şərh yaz

Translate »