Ən uzun gözəl alt sətir LeetCode Həlli

Çətinlik səviyyəsi Asan
Tez-tez soruşulur microsoftBaxılıb 72

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat :

Ən uzun gözəl alt sətir LeetCode Həlli – A sətri s-dir gözəl s olan əlifbanın hər hərfi üçün görünür həm böyük və kiçik hərflərlə. Məsələn, "abABB" gözəldir, çünki "A" və "a" görünür, "B" və "b" görünür. Bununla belə, “abA” “b” göründüyü üçün deyil, “B” görünmür.

s sətri verilmişdir, qayıt ən uzun alt sətir s yəni gözəl. Bir neçə varsa, alt sətirini qaytarın ən erkən baş verməsi. Heç biri yoxdursa, boş bir sətir qaytarın.

Misal:

Məsələn 1

Input: s = "YazaAay"
Output: "aAa"
Explanation: "aAa" is a nice string because 'A/a' is the only letter of the alphabet in s, and both 'A' and 'a' appear.
"aAa" is the longest nice substring.

Məsələn 2 

Input: s = "Bb"
Output: "Bb"
Explanation: "Bb" is a nice string because both 'B' and 'b' appear. The whole string is a substring.

Məsələn 3

Input: s = "c"
Output: ""
Explanation: There are no nice substrings.

Məhdudiyyətlər:

Ən uzun gözəl alt sətir LeetCode Həlli

İzahat:

  • Biz qayıtmalıyıq ən uzun alt sətir s yəni gözəl.
  • s sətridir gözəl s olan əlifbanın hər hərfi üçün görünür həm böyük və kiçik hərflərlə.
  • tapa bilsək çox cavablar, onda etməliyik alt sətirini qaytarın ən erkən baş verməsi. Heç biri yoxdursa, boş bir sətir qaytarın.

Yanaşma:

  • Əvvəlcə necə yoxlaya biləcəyimizi anlamalıyıq sim gözəldirsə yoxsa yox.
  • Simin olub olmadığını yoxlamaq üçün gözəl or yox, a istifadə edə bilərik təyin etmək, yoxsa böyük hərf or kiçik hər hansı əlifbanın simvolları dəstdə mövcuddur, bu o deməkdir ki, s sətri gözəl sətir deyil.
  • Sətir gözəldirsə, o deməkdir ki, sətirdə mövcud olan bütün əlifbalar kiçik və böyük hərflərə malikdir. həmin Stringi qaytarın, çünki biz qayıtmalıyıq ən uzun gözəl alt sətir.
  • Sətir gözəl deyilsə, bir xarakter var bütün sətirin qarşısını alır kimi gözəl olmaqdan.
  • belə ki, gözəl alt sətir tapmaq üçün yeganə yoldur bu simvolu istisna edin, bu sizin deməkdir sətri həmin simvola bölün, x deyin, kimi bir şey [start…]x[…end]

  • İndi ikimiz var alt problemlər ilə sol və sağ alt problemlər. Beləliklə, orijinalı tapmaq üçün Ən uzun gözəl alt sətir problem, biz edə bilərik rekursiv olaraq yaxınlaşın. Bu tərifin özüdür Böl və qalib gəl texnikası - Böl və idarə et alqoritmi problemi rekursiv şəkildə eyni və ya əlaqəli tipli iki və ya daha çox alt problemə parçalayır, onlar birbaşa həll oluna biləcək qədər sadələşir. Daha sonra ilkin problemin həllini vermək üçün alt problemlərin həlli yolları birləşdirilir.

Kod:

Java Kodu ən uzun gözəl alt sətir:

class Solution {
  public String longestNiceSubstring(String s) {
  int[] niceSubstring = longestNiceSubstring(s,0,s.length()-1);
  return s.substring(niceSubstring[0], niceSubstring[1]+1);
}
    
private int[]  longestNiceSubstring(String s,int left,int right) {
  int splittingIndex=isNotNiceString(s,left,right);
if(splittingIndex==-1)return  new int[]{left, right};
            int[]  leftString = longestNiceSubstring(s,left,splittingIndex-1);
      int[]  rightString = longestNiceSubstring(s,splittingIndex+1,right);
      return  (leftString[1]-leftString[0]>= rightString[1]-rightString[0]) ? leftString : rightString;

}
    
private int isNotNiceString(String s,int left,int right) {
        Set<Character> set = getCharacterSet(s,left,right);    
        for (int i = left; i <=right; i++) {
            char ch = s.charAt(i);
            if (!set.contains(Character.toLowerCase(ch)) || !set.contains(Character.toUpperCase(ch))) {
                return i;
            }
        }
        return -1;
    }
    
private Set<Character> getCharacterSet(String s, int left, int right) {
  Set<Character> charSet = new HashSet<Character>();
  for (int i = left; i <= right; i++){
    charSet.add(s.charAt(i));
    }
  return charSet;
}
}

C++ Kodu Ən uzun gözəl alt sətir:

class Solution {
public:
    string longestNiceSubstring(string s) {
          
   pair<int,int> niceSubstring = longestNiceSubstring(s,0,s.length()-1);
  return s.substr(niceSubstring.first, niceSubstring.second-niceSubstring.first+1);
}
    
 pair<int,int> longestNiceSubstring(string&s,int left,int right) {
  int splittingIndex=isNotNiceString(s,left,right);
     pair<int,int> rez = {left,right};
if(splittingIndex==-1)return  rez;
            pair<int,int> leftString = longestNiceSubstring(s,left,splittingIndex-1);
      pair<int,int> rightString = longestNiceSubstring(s,splittingIndex+1,right);
      return  (leftString.second-leftString.first>= rightString.second-rightString.first) ? leftString : rightString;

}
    
 int isNotNiceString(string&s,int left,int right) {
       unordered_set<char>  set = getCharacterSet(s,left,right);    
        for (int i = left; i <=right; i++) {
            char ch = s[i];
            if (set.find(toupper(ch))==set.end() ||set.find(tolower(ch))==set.end()) {
                return i;
            }
        }
        return -1;
    }
    
  unordered_set<char> getCharacterSet(string&s, int left, int right) {
   unordered_set<char>charSet; 
  for (int i = left; i <= right; i++){
    charSet.insert(s[i]);
    }
  return charSet;
} 
    
};

Ən uzun gözəl alt sətir LeetCode Həlli üçün Mürəkkəblik Təhlili:

Zamanın mürəkkəbliyi

O(n) , çünki Böl və fəth et rekursiv yanaşma simin uzunluğunu keçəcək.

Kosmik Mürəkkəblik 

O(1) , rekursiya yığını sahəsindən başqa, dəstdə ən çoxu 52 böyük və kiçik hərflər olacaq.

 

Crack Sistemi Dizayn Müsahibələri
Translate »