הפוך את מחרוזת לפתרון Leetcode נהדר


רמת קושי קַל
נשאל לעתים קרובות Google
LeetCode לערום מחרוזת

הצהרת בעיה

בבעיה "הפוך את המחרוזת נהדרת" ניתן מחרוזת המורכבת מאותיות קטנות וקטנות. עלינו להפוך את המחרוזת הזו לטובה על ידי הסרת תווים סמוכים במחרוזת שהופכת את המחרוזת לרעה.
מחרוזת טובה היא מחרוזת שאין בה שתי תווים סמוכים כאשר שתי הדמויות זהות אך באותה מקרה. אנו יכולים לבצע פעולה זו מספר פעמים כדי להפוך את המחרוזת לטובה.

דוגמה

s = "leEeetcode"
"leetcode"

הסבר:

בשלב הראשון, אנו יכולים לבחור באינדקס 1 ו -2 או 2 ו -3, שניהם יפחיתו את "leEeetcode" ל- "leetcode".

"abBAcC"
""

הסבר:

תרחישים אפשריים הם:
הפוך את מחרוזת לפתרון Leetcode נהדר

גישה

למחרוזת הנתונה יש אופי צמוד זהה אך למקרה הפוך. אז מה שעלינו לעשות הוא בכל פעם שאנו נתקלים בשתי הדמויות הללו עלינו להסיר את שתיהן ושוב לחזור על התהליך עבור המחרוזת שנותרה.

בשביל זה מה שאנחנו יכולים לעשות זה שנוכל לחזור מהדמות הראשונה של המחרוזת הנתונה ולצרף את הדמות למחרוזת התוצאה שלנו עד שהיא לא רעה.
לפני שמוסיפים את הדמות הנוכחית נבדוק אם צירוף של תו זה למחרוזת res יגרום לו להיות רע או לא על ידי השוואתו לתו האחרון של מחרוזת res. אם הבדל אינטגרלי (ASCII) בין שתי הדמויות האלה שווה 32 ואז זה שילוב גרוע אחרת זה טוב. על בסיס זה אנו מבצעים את הפעולות הבאות:

  • אם צירוף הדמות לא יעשה רע, פשוט נצרף את הדמות הזו למילואים.
  • אחרת, לא נספח ונסיר את התו האחרון של מחרוזת res.

עבור האלגוריתם הנ"ל נוכל להשתמש בו לערום מבנה נתונים לדחיפת דמות לסוף והוצאת דמות מהסוף.
ב- C ++ אנו יכולים גם להשתמש כיתת מיתרים כערימת תווים ויכולה להשתמש בפעולות push_back () ו- pop_back () כמו מחלקת stack.

יישום

תוכנית C ++ להכנת מחרוזת לפתרון Leetcode נהדר

#include <bits/stdc++.h>
using namespace std;

string makeGood(string s) {

    string goodString;

    for(char ch:s)
    {
        if((!goodString.empty()) && abs(goodString.back()-ch)==32)  
            goodString.pop_back();
        else  
            goodString.push_back(ch);
    }

    return goodString;
}

int main() 
{
    string s = "leEeetcode";
    
    cout<<makeGood(s)<<endl;

  return 0; 
}
"leetcode"

תוכנית Java להכנת מחרוזת לפתרון Leetcode נהדר

import java.lang.*;
import java.util.*;

class Rextester
{  
    public static String makeGood(String s) {

        Stack<Character> stack= new Stack<Character>();

        for(int i=0;i<s.length();i++)
        {
            if((!stack.isEmpty()) && Math.abs(stack.peek()-s.charAt(i))==32 )
                stack.pop();
            else
                stack.push(s.charAt(i));
        }

        char res[]= new char[stack.size()];
        
        for(int i=res.length-1;i>=0;i--) 
            res[i]= stack.pop();

        return new String(res);

    }
    
    public static void main(String args[])
    {
        String s = "leEeetcode";

        System.out.println(makeGood(s));
        
    }
}
"leetcode"

ניתוח מורכבות כדי להפוך את המחרוזת לפתרון Leetcode נהדר

מורכבות זמן

O (n): כאשר n הוא אורך מחרוזת הקלט. כי אנחנו חוזרים דרך המחרוזת בלולאה אחת. מכאן שמורכבות הזמן תהיה בסדר גודל של n.

מורכבות בחלל 

O (n): אנו משתמשים בערימה כדי לאחסן את התוצאה הסופית שלנו. מכאן שהמרווח המשמש יהיה בסדר n, כלומר O (n).