String LeetCode Həllində ilk unikal simvol

Problem bəyanat

Simli LeetCode Həllində ilk unikal simvol – sətir verilmişdir s, içindəki ilk təkrarlanmayan simvolu tapın və indeksini qaytarın. Əgər mövcud deyilsə, geri qayıdın -1.

misal

Test işi 1:

Input:

s = “leetcode”

Çıxış:

0

Test işi 2:

Input:

s = “aabb”

Çıxış:

-1

Izahat

i) Birinci sınaq vəziyyətində 'l' ilk unikal simvoldur. 'l' indeksi 0-dır.

ii) İkinci sınaq vəziyyətində unikal xarakter yoxdur. Beləliklə, biz -1 qayıdırıq.

Yanaşma:

Əsas ideyanın qısa versiyası: İki keçiddən keçir giriş sətri. İlk keçiddə hər bir simvolun neçə dəfə göründüyünü saya bilərik. İkinci keçiddə sətirdə bir dəfə görünən ilk simvolu qaytarın.

Əsas ideyanın uzun versiyası: Unikal xarakter məhz bir dəfə görünən personajdır. Nə çox, nə də az. Beləliklə, edə bilərik

1. keçmək sim sətirdəki hər simvolun neçə dəfə göründüyünü izləmək üçün
2. Tam bir dəfə görünən simvolu tapmaq üçün sətri yenidən keçin, onun indeksini qaytarın
3. Əgər heç bir simvol tam olaraq bir dəfə görünməyibsə -1 qaytarın

Hər simvolun sayını izləmək üçün biz ölçüsü 26 olan int[] chrs-ni işə salırıq. İlk keçiddən sonra i indeksindəki hər bir element əlifbanın i-ci simvolunun sətirdə görünmə sayını göstərəcək. Beləliklə, chrs[0] 'a'nın görünmə sayını, chrs[5] isə əlifbanın 5-ci elementi olan 'e'nin görünmə sayını təmsil edəcək. Hər simvolu təmsil edən chrs[] elementinə daxil olmaq üçün həmin simvoldan 'a' çıxırıq.

Məsələn, 'a' – 'a' 0 ilə nəticələnir -> Mükəmməl düzülür, çünki 'a' əlifbada 0-cı elementdir
Başqa bir misal, 'e' – 'a', nəticə 5 -> Mükəmməl düzülür, çünki 'e' əlifbada 5-ci elementdir

Sonra, ikinci keçiddə biz sadəcə olaraq bir dəfə görünən ilk elementi axtarırıq. Biz hər simvolun təmsilçisi olan chrs[] elementinə daxil olmaq üçün eyni "a" çıxarma hiyləsindən istifadə edirik. Nəhayət, heç biri tam olaraq bir dəfə görünməsə, -1-i qaytarırıq.

Sətirdəki ilk unikal simvol üçün kod

Java Proqramı

class Solution {
    public int firstUniqChar(String s) {
        int len = s.length();
        
        if(len == 0){
            return -1;
        }
        
        int[] arr = new int[26];
        
        for(char c : s.toCharArray()){
            arr[c - 'a']++;
        }
        
        for(int i=0; i<len; i++){
            if(arr[s.charAt(i) - 'a'] == 1){
                return i;
            }
        }
        
        return -1;
    }
}

C ++ Proqramı

class Solution {
public:
    int firstUniqChar(string s) {
        map<char, int> G; // Map char to its count in the string
        for (int i{}; i < s.size(); i++) { 
      G[s[i]]++;  // Everytime the character appears in the string, add one to its count
    } 
        for (int i{}; i < s.size(); i++) { // Start traversing the string from the beginning. 
      if (G[s[i]] == 1) return i; // If the count of the char is equal to 1, it is the first distinct character in the list.
    } 
        return -1;
    }
};

String LeetCode Həllində İlk Unikal Xarakter üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi: O (n)

Kosmik Mürəkkəblik: O (1) sabit məkandan istifadə etdiyimiz üçün.