സ്ട്രിംഗ് മികച്ച ലീറ്റ്കോഡ് പരിഹാരമാക്കുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ഗൂഗിൾ
ലീട്ട് കോഡ് കൂനകൂട്ടുക സ്ട്രിംഗ്

പ്രശ്നം പ്രസ്താവന

“സ്‌ട്രിംഗ് മികച്ചതാക്കുക” പ്രശ്‌നത്തിൽ ഒരു സ്‌ട്രിംഗിന് ചെറിയ, വലിയ അക്ഷരങ്ങൾ അടങ്ങിയിരിക്കുന്നു. സ്‌ട്രിംഗിനെ മോശമാക്കുന്ന സ്‌ട്രിംഗിലെ അടുത്ത പ്രതീകങ്ങൾ നീക്കംചെയ്‌ത് ഞങ്ങൾ ഈ സ്‌ട്രിംഗ് മികച്ചതാക്കണം.
ഒരു നല്ല സ്ട്രിംഗ് ഒരു സ്ട്രിംഗാണ്, അതിൽ രണ്ട് പ്രതീകങ്ങളും തുല്യമാണെങ്കിലും വ്യത്യസ്ത കേസുകളുള്ള രണ്ട് അടുത്ത പ്രതീകങ്ങളില്ല. സ്ട്രിംഗ് മികച്ചതാക്കാൻ നമുക്ക് എത്ര തവണ ഈ പ്രവർത്തനം ചെയ്യാൻ കഴിയും.

ഉദാഹരണം

s = "leEeetcode"
"leetcode"

വിശദീകരണം:

ആദ്യ ഘട്ടത്തിൽ, നമുക്ക് സൂചിക 1, 2 അല്ലെങ്കിൽ 2, 3 എന്നിവ തിരഞ്ഞെടുക്കാം, രണ്ടും “ലീഇറ്റ്കോഡ്” “ലീറ്റ്കോഡ്” ആയി കുറയ്ക്കും.

"abBAcC"
""

വിശദീകരണം:

സാധ്യമായ സാഹചര്യങ്ങൾ ഇവയാണ്:
സ്ട്രിംഗ് മികച്ച ലീറ്റ്കോഡ് പരിഹാരമാക്കുക

സമീപനം

തന്നിരിക്കുന്ന സ്‌ട്രിംഗിന് സമാനമായ ചില വിപരീത പ്രതീകങ്ങളുണ്ട്. അതിനാൽ നമ്മൾ ചെയ്യേണ്ടത് ഈ രണ്ട് പ്രതീകങ്ങൾ കണ്ടുമുട്ടുമ്പോഴെല്ലാം അവ രണ്ടും നീക്കംചെയ്യുകയും ശേഷിക്കുന്ന സ്ട്രിംഗിനായി വീണ്ടും ആവർത്തിക്കുകയും വേണം.

ഇതിനായി നമുക്ക് ചെയ്യാൻ കഴിയുന്നത്, തന്നിരിക്കുന്ന സ്‌ട്രിംഗിന്റെ ആദ്യ പ്രതീകത്തിൽ നിന്ന് ആവർത്തനം ചെയ്യാനും പ്രതീകത്തെ ഞങ്ങളുടെ ഫല സ്‌ട്രിംഗിലേക്ക് ചേർക്കാനും കഴിയും, അത് മോശമല്ല.
നിലവിലെ പ്രതീകം കൂട്ടിച്ചേർക്കുന്നതിനുമുമ്പ്, ഈ പ്രതീകം റെസ് സ്ട്രിംഗിലേക്ക് ചേർക്കുന്നത് മോശമാകുമോ അതോ റെസ് സ്ട്രിംഗിന്റെ അവസാന പ്രതീകവുമായി താരതമ്യപ്പെടുത്തിക്കൊണ്ടോ എന്ന് ഞങ്ങൾ പരിശോധിക്കും. അവിഭാജ്യ വ്യത്യാസമുണ്ടെങ്കിൽ (ASCII) ആ രണ്ട് പ്രതീകങ്ങൾക്കിടയിൽ 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"

സ്ട്രിംഗ് മികച്ച ലീറ്റ്കോഡ് പരിഹാരമാക്കുന്നതിനുള്ള സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n): ഇൻപുട്ട് സ്ട്രിംഗിന്റെ നീളം ഇവിടെ n ആണ്. കാരണം ഞങ്ങൾ ഒരൊറ്റ ലൂപ്പിലെ സ്ട്രിംഗിലൂടെ ആവർത്തിക്കുന്നു. അതിനാൽ സമയ സങ്കീർണ്ണത n ന്റെ ക്രമമായിരിക്കും.

ബഹിരാകാശ സങ്കീർണ്ണത 

O (n): ഞങ്ങളുടെ അന്തിമഫലം സംഭരിക്കാൻ ഞങ്ങൾ ഒരു സ്റ്റാക്ക് ഉപയോഗിക്കുന്നു. അതിനാൽ ഉപയോഗിക്കുന്ന ഇടം n, അതായത് O (n) ന്റെ ക്രമമായിരിക്കും.