Зробіть String чудовим рішенням для штрих-коду


Рівень складності Легко
Часто запитують у Google
LeetCode Стек рядок

Постановка проблеми

У задачі “Зробіть рядок великою” задається рядок, що складається з малих та великих літер. Ми повинні зробити цей рядок хорошим, видаливши сусідні символи в рядку, що робить рядок поганим.
Хороший рядок - це рядок, який не має двох сусідніх символів, де обидва символи однакові, але мають різний регістр. Ми можемо зробити цю операцію будь-яку кількість разів, щоб зробити рядок хорошим.

Приклад

s = "leEeetcode"
"leetcode"

Пояснення:

На першому кроці ми можемо вибрати індекс 1 і 2 або 2 і 3, обидва зменшать “leEeetcode” до “leetcode”.

"abBAcC"
""

Пояснення:

Можливі сценарії:
Зробіть String чудовим рішенням для штрих-коду

Підхід

Даний рядок має деякий сусідній символ, який є однаковим, але в протилежному випадку. Отже, що нам потрібно робити, це коли ми стикаємось із цими двома символами, ми повинні їх видалити і знову повторювати процес для решти рядка.

Для цього ми можемо зробити те, що ми можемо виконати ітерацію з першого символу заданого рядка і додати символ до нашого рядка результатів, поки це не буде погано.
Перед додаванням поточного символу ми перевіримо, чи додавання цього символу до рядка res зробить його поганим чи ні, порівнявши його з останнім символом рядка res. Якщо інтегральна різниця (ASCII) між цими двома символами дорівнює 32, тоді це погана комбінація, інакше це добре. На підставі цього ми зробимо наступну операцію:

  • якщо додавання символу не буде поганим, ми просто додамо цей символ до res.
  • В іншому випадку ми не додамо і видалимо останній символ рядка res.

Для вищезазначеного алгоритму ми можемо використовувати стек структура даних для висунення символу до кінця та видалення символу з кінця.
У C ++ ми також можемо використовувати клас рядків як стек символів і може використовувати операції push_back () та pop_back (), як клас стека.

Реалізація

Програма C ++ для створення чудового рішення для струнного коду

#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).