Palindrom Permutasiyası LeetCode Həlli

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Bloomberg Facebook Goldman Sachs google microsoft Über
metaBaxılıb 21

Problem bəyanat

Palindrom Permutasiyası LeetCode Həlli – Bizə sətir verilir və verilən sətirin dəyişdirilməsinin palindromu yarada biləcəyini soruşurlar.

Nümunələr və izahatlar

Misal 1:

Input: s = "code"
Output: false
Explanation: we can not arrange letters of "code" to form a palindrome

Misal 2:
Input: s = "aab"
Output: true
Explanation: permutation "aba" of given string is palindrome, hence true

Misal 3:
Input: s = "carerac"
Output: true
Explanation: the given string is itself palindrome, there exists multiple permuations that form palindrome

Yanaşma

Bir sim düzəltmək üçün palindrom, bizə hərflərin cüt sayda təkrarlanması lazımdır ki, sətir soldan və sağdan eyni oxusun. Gəlin “cüt” hərfinin bu sol və sağ halını adlandıraq. Eyni hərfin 1 cütdən çoxu ola bilər, məsələn. “aaaaaa” da palindromdur. Sətin tək uzunluqda olması halında, cüt olmayan yalnız bir hərfə icazə verilir, məsələn. “aaxaa”, 'x' heç bir ortağı yoxdur, ona görə də cüt əmələ gəlmir. Bu, bizə bu problemi həll etmək üçün intuisiya verməlidir.

Alqoritm

Hashmapdan istifadə edərək hər hərfin baş vermə sayını sayacağıq. Sətirdəki hər hərfi təkrarlayın və baş verənləri saymaq üçün hər simvolun dəyərini artırın. Hər hərfin bütün saylarını çeşidlədikdən sonra dəyərlərə baxırıq.

  • əgər say cüt olarsa - bu o deməkdir ki, bu, bizə palindrom yaratmağa kömək edəcək, heç nə etmə
  • sayı təkdirsə - bu, deməkdir palindrom başqa heç bir hərfin tək say dəyəri yoxdursa mümkündür, tək sayma dəyəri ilə qarşılaşdığımız zaman izləmək üçün isCountOdd dəyişənini saxlayın
  • isCountOdd 1-dirsə, bu o deməkdir ki, bizdə artıq qəribə bir hərf var, ona görə də simvolun say dəyərinə baxırıq
    • bərabərdirsə - heç nə etməyin
    • təkdirsə - palindrom mümkün deyil

isCountOdd göstəricisindən istifadə etmək əvəzinə biz map%2-nin dəyərlərini saxlayacaq başqa count dəyişəndən istifadə edə bilərik. Əgər bütün hərflər cüt dəfə görünürsə, say 0 olaraq qalacaq. Tək hallar olduqda, say 1 artırılacaq. Əgər say ≤ 1 ⇒ palindrom mümkündürsə. Bu yanaşma java kodunda göstərilir.

Kodu

Palindrome Permutation LeetCode Solution üçün C++ kodu

class Solution {
public:
    bool canPermutePalindrome(string s) {
        unordered_map<char,int> cnt;
        int n=s.size();
        for(int i=0; i<n; i++) {
            cnt[s[i]]++;
        }
        int isCountOdd=0;
        
        for(auto it:cnt){
            if(isCountOdd==1 && it.second%2!=0) return 0;
            else if(it.second%2!=0) isCountOdd++;
            else continue;
        }
        return 1;
    }
};

Palindrome Permutation LeetCode Solution üçün Java kodu

public class Solution {
    public boolean canPermutePalindrome(String s) {
        int[] map = new int[128];
        for (int i = 0; i < s.length(); i++) {
            map[s.charAt(i)]++;
        }
        int count = 0;
        for (int key = 0; key < map.length && count <= 1; key++) {
            count += map[key] % 2;
        }
        return count <= 1;
    }
}

Mürəkkəblik təhlili

  • Zamanın mürəkkəbliyi: O (n)
    • 2 döngə istifadə olunur, biri O(n) ilə baş verən hadisələri saymaq üçün, digəri isə ən pis halda O(n) vaxtını alaraq yenidən s sətirinin fərqli elementləri üzərində keçmək üçün istifadə olunur, yəni s-dəki bütün simvollar fərqlidir.
  • Kosmik mürəkkəblik: O (1)
    • Xəritə bütün fərqli elementlərin maksimum sayına qədər böyüyə bilər. Bununla belə, fərqli simvolların sayı məhduddur və kosmik mürəkkəblik də məhduddur.
Translate »