ಸ್ಟ್ರಿಂಗ್ ಗ್ರೇಟ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ಮಾಡಿ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಗೂಗಲ್
ಲೀಟ್‌ಕೋಡ್ ಸ್ಟಾಕ್ ಸ್ಟ್ರಿಂಗ್

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

“ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಗ್ರೇಟ್ ಮಾಡಿ” ಸಮಸ್ಯೆಯಲ್ಲಿ ಸ್ಟ್ರಿಂಗ್ ನೀಡಲಾಗಿದೆ ಸಣ್ಣ ಮತ್ತು ದೊಡ್ಡ ಅಕ್ಷರಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಸ್ಟ್ರಿಂಗ್‌ನಲ್ಲಿನ ಪಕ್ಕದ ಅಕ್ಷರಗಳನ್ನು ತೆಗೆದುಹಾಕುವುದರ ಮೂಲಕ ನಾವು ಈ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಉತ್ತಮಗೊಳಿಸಬೇಕು ಅದು ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಕೆಟ್ಟದಾಗಿ ಮಾಡುತ್ತದೆ.
ಉತ್ತಮ ಸ್ಟ್ರಿಂಗ್ ಎನ್ನುವುದು ಎರಡು ಪಕ್ಕದ ಅಕ್ಷರಗಳನ್ನು ಹೊಂದಿರದ ಸ್ಟ್ರಿಂಗ್ ಆಗಿದ್ದು, ಅಲ್ಲಿ ಎರಡೂ ಅಕ್ಷರಗಳು ಒಂದೇ ಆದರೆ ವಿಭಿನ್ನ ಸಂದರ್ಭದಲ್ಲಿರುತ್ತವೆ. ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಉತ್ತಮಗೊಳಿಸಲು ನಾವು ಈ ಕಾರ್ಯಾಚರಣೆಯನ್ನು ಎಷ್ಟು ಬಾರಿ ಮಾಡಬಹುದು.

ಉದಾಹರಣೆ

s = "leEeetcode"
"leetcode"

ವಿವರಣೆ:

ಮೊದಲ ಹಂತದಲ್ಲಿ, ನಾವು ಸೂಚ್ಯಂಕ 1 ಮತ್ತು 2 ಅಥವಾ 2 ಮತ್ತು 3 ಅನ್ನು ಆಯ್ಕೆ ಮಾಡಬಹುದು, ಎರಡೂ “ಲೀಇಟ್‌ಕೋಡ್” ಅನ್ನು “ಲೀಟ್‌ಕೋಡ್” ಗೆ ಕಡಿಮೆ ಮಾಡುತ್ತದೆ.

"abBAcC"
""

ವಿವರಣೆ:

ಸಂಭವನೀಯ ಸನ್ನಿವೇಶಗಳು ಹೀಗಿವೆ:
ಸ್ಟ್ರಿಂಗ್ ಗ್ರೇಟ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ಮಾಡಿ

ಅಪ್ರೋಚ್

ಕೊಟ್ಟಿರುವ ಸ್ಟ್ರಿಂಗ್ ಕೆಲವು ಪಕ್ಕದ ಅಕ್ಷರಗಳನ್ನು ಹೊಂದಿದೆ ಆದರೆ ಅದು ಒಂದೇ ಆದರೆ ವಿರುದ್ಧವಾಗಿರುತ್ತದೆ. ಆದ್ದರಿಂದ ನಾವು ಮಾಡಬೇಕಾಗಿರುವುದು ಈ ಎರಡು ಅಕ್ಷರಗಳನ್ನು ನಾವು ಎದುರಿಸಿದಾಗಲೆಲ್ಲಾ ನಾವು ಅವೆರಡನ್ನೂ ತೆಗೆದುಹಾಕಬೇಕು ಮತ್ತು ಉಳಿದ ಸ್ಟ್ರಿಂಗ್‌ಗಾಗಿ ಮತ್ತೆ ಪ್ರಕ್ರಿಯೆಯನ್ನು ಪುನರಾವರ್ತಿಸಬೇಕು.

ಇದಕ್ಕಾಗಿ ನಾವು ಏನು ಮಾಡಬಹುದೆಂದರೆ, ಕೊಟ್ಟಿರುವ ಸ್ಟ್ರಿಂಗ್‌ನ ಮೊದಲ ಅಕ್ಷರದಿಂದ ನಾವು ಪುನರಾವರ್ತಿಸಬಹುದು ಮತ್ತು ಪಾತ್ರವನ್ನು ನಮ್ಮ ಫಲಿತಾಂಶದ ಸ್ಟ್ರಿಂಗ್‌ಗೆ ಸೇರಿಸಬಹುದು ಅದು ಕೆಟ್ಟದ್ದಲ್ಲ.
ಪ್ರಸ್ತುತ ಅಕ್ಷರವನ್ನು ಸೇರಿಸುವ ಮೊದಲು ನಾವು ಈ ಅಕ್ಷರವನ್ನು ರೆಸ್ ಸ್ಟ್ರಿಂಗ್‌ಗೆ ಸೇರಿಸುವುದರಿಂದ ಅದನ್ನು ರೆಸ್ ಸ್ಟ್ರಿಂಗ್‌ನ ಕೊನೆಯ ಅಕ್ಷರದೊಂದಿಗೆ ಹೋಲಿಸುವ ಮೂಲಕ ಕೆಟ್ಟದಾಗುತ್ತದೆಯೇ ಅಥವಾ ಇಲ್ಲವೇ ಎಂದು ಪರಿಶೀಲಿಸುತ್ತೇವೆ. ಅವಿಭಾಜ್ಯ ವ್ಯತ್ಯಾಸವಿದ್ದರೆ (ಎಎಸ್ಸಿಐಐ) ಆ ಎರಡು ಅಕ್ಷರಗಳ ನಡುವೆ 32 ಕ್ಕೆ ಸಮಾನವಾಗಿರುತ್ತದೆ ನಂತರ ಅದು ಕೆಟ್ಟ ಸಂಯೋಜನೆಯಾಗಿದೆ ಇಲ್ಲದಿದ್ದರೆ ಅದು ಒಳ್ಳೆಯದು. ಅದರ ಆಧಾರದ ಮೇಲೆ ನಾವು ಈ ಕೆಳಗಿನ ಕಾರ್ಯಾಚರಣೆಯನ್ನು ಮಾಡುತ್ತೇವೆ:

  • ಪಾತ್ರವನ್ನು ಸೇರಿಸುವುದರಿಂದ ಕೆಟ್ಟದ್ದಲ್ಲ, ನಾವು ಆ ಪಾತ್ರವನ್ನು ರೆಸ್‌ಗೆ ಸೇರಿಸುತ್ತೇವೆ.
  • ಬೇರೆ, ನಾವು ಸೇರ್ಪಡೆಗೊಳ್ಳುವುದಿಲ್ಲ ಮತ್ತು ರೆಸ್ ಸ್ಟ್ರಿಂಗ್‌ನ ಕೊನೆಯ ಅಕ್ಷರವನ್ನು ತೆಗೆದುಹಾಕುತ್ತೇವೆ.

ಮೇಲಿನ ಅಲ್ಗಾರಿದಮ್ಗಾಗಿ ನಾವು ಬಳಸಬಹುದು ಸ್ಟಾಕ್ ಅಕ್ಷರವನ್ನು ಅಂತ್ಯಕ್ಕೆ ತಳ್ಳಲು ಮತ್ತು ಕೊನೆಯಿಂದ ಅಕ್ಷರವನ್ನು ಹೊರಹಾಕಲು ಡೇಟಾ ರಚನೆ.
ಸಿ ++ ನಲ್ಲಿ ನಾವು ಸಹ ಬಳಸಬಹುದು ಸ್ಟ್ರಿಂಗ್ ವರ್ಗ ಅಕ್ಷರಗಳ ಸಂಗ್ರಹವಾಗಿ ಮತ್ತು ಸ್ಟಾಕ್ ವರ್ಗದಂತಹ ಪುಶ್_ಬ್ಯಾಕ್ () ಮತ್ತು ಪಾಪ್_ಬ್ಯಾಕ್ () ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ಬಳಸಬಹುದು.

ಅನುಷ್ಠಾನ

ಸ್ಟ್ರಿಂಗ್ ಗ್ರೇಟ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕಾಗಿ ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#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"

ಸ್ಟ್ರಿಂಗ್ ಗ್ರೇಟ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕಾಗಿ ಜಾವಾ ಪ್ರೋಗ್ರಾಂ

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"

ಸ್ಟ್ರಿಂಗ್ ಗ್ರೇಟ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕಾಗಿ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್): ಇಲ್ಲಿ n ಎಂಬುದು ಇನ್ಪುಟ್ ಸ್ಟ್ರಿಂಗ್ನ ಉದ್ದವಾಗಿದೆ. ಏಕೆಂದರೆ ನಾವು ಒಂದೇ ಲೂಪ್‌ನಲ್ಲಿ ಸ್ಟ್ರಿಂಗ್ ಮೂಲಕ ಪುನರಾವರ್ತಿಸುತ್ತಿದ್ದೇವೆ. ಆದ್ದರಿಂದ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು n ನ ಕ್ರಮವಾಗಿರುತ್ತದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ 

ಒ (ಎನ್): ನಮ್ಮ ಅಂತಿಮ ಫಲಿತಾಂಶವನ್ನು ಸಂಗ್ರಹಿಸಲು ನಾವು ಸ್ಟಾಕ್ ಅನ್ನು ಬಳಸುತ್ತಿದ್ದೇವೆ. ಆದ್ದರಿಂದ ಬಳಸಿದ ಸ್ಥಳವು n ನ ಕ್ರಮವಾಗಿರುತ್ತದೆ, ಅಂದರೆ O (n).