ക്രാളർ ലോഗ് ഫോൾഡർ ലീറ്റ്കോഡ് പരിഹാരം


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു മെർക്കാരി
കൂനകൂട്ടുക

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

ഈ പ്രശ്‌നത്തിൽ, ഒരു ഫോൾഡർ സിസ്റ്റത്തിലെ ഞങ്ങളുടെ സ്ഥാനം ഞങ്ങൾ ട്രാക്കുചെയ്യുന്നു. ഞങ്ങൾ തുടക്കത്തിൽ റൂട്ട് ഫോൾഡറിലോ ഈ സിസ്റ്റത്തിന്റെ പ്രധാന ഫോൾഡറിലോ ആണ്.
ഞങ്ങൾക്ക് അടിസ്ഥാനപരമായി 3 തരം കമാൻഡുകൾ ഇവിടെയുണ്ട്. ഓരോ സ്ട്രിംഗിനും ഒരു കമാൻഡ് അർത്ഥമാക്കുന്ന സ്ട്രിംഗിന്റെ രൂപത്തിലാണ് കമാൻഡുകൾ.

  •  “../” എന്നാൽ നിലവിലെ ഫോൾഡറിന്റെ പാരന്റ് ഫോൾഡറിലേക്ക് പോകുക (ഇതിനകം റൂട്ട് ഫോൾഡറിലാണെങ്കിൽ എവിടെയും പോകരുത്).
  •  “./” നിലവിലെ ഫോൾഡറിൽ തുടരുക.
  •  “X /” x എന്ന പേരുള്ള നിലവിലെ ഫോൾഡറിന്റെ ചൈൽഡ് ഫോൾഡറിലേക്ക് പോകുക.

മുകളിലുള്ള 3 കമാൻഡുകളുടെ സംയോജനമായ കമാൻഡുകളുടെ ഒരു ശ്രേണി ഞങ്ങൾക്ക് നൽകിയിരിക്കുന്നു. തന്നിരിക്കുന്ന കമാൻഡുകൾ മുൻകൂട്ടി തയ്യാറാക്കിയ ശേഷം റൂട്ട് ഫോൾഡറിലേക്ക് മടങ്ങാനുള്ള ഏറ്റവും കുറഞ്ഞ പ്രവർത്തന എണ്ണം ഞങ്ങൾ കണ്ടെത്തണം.
ഉദാ
ലോഗുകൾ = [“d1 /”, ”d2 /","../”, ”d21 /","./”]

ക്രാളർ ലോഗ് ഫോൾഡർ ലീറ്റ്കോഡ് പരിഹാരം
റൂട്ട് ഫോൾഡറിൽ നിന്നുള്ള 2 ആഴത്തിലാണ് ഞങ്ങൾ. അതിനാൽ, ഞങ്ങളുടെ ഉത്തരം 2 ആയിരിക്കും.

ഉദാഹരണം

logs = ["d1/","d2/","../","d21/","./"]
2

വിശദീകരണം:

ഈ മാറ്റ ഫോൾഡർ പ്രവർത്തനം “../” 2 തവണ ഉപയോഗിച്ച് പ്രധാന ഫോൾഡറിലേക്ക് മടങ്ങുക.

logs = ["d1/","d2/","./","d3/","../","d31/"]
3

സമീപനം 1 (സ്റ്റാക്ക് ഉപയോഗിക്കുന്നു)

ഞങ്ങൾക്ക് ഫയൽ നാമങ്ങളുടെ ഒരു ശേഖരം ഉപയോഗിക്കാം. തുടക്കത്തിൽ ഞങ്ങളുടെ സ്റ്റാക്ക് ശൂന്യമാണ്. നമുക്ക് ഒരു സബ്ഫോൾഡറിലേക്ക് പോകേണ്ടി വരുമ്പോഴെല്ലാം സബ്ഫോൾഡറിന്റെ പേര് സ്റ്റാക്കിലേക്ക് തള്ളപ്പെടും. അതിനാൽ, ഞങ്ങൾ നിലവിൽ ഉള്ള ഫോൾഡർ എല്ലായ്പ്പോഴും സ്റ്റാക്കിന്റെ മുകളിൽ തുടരും.
അതിനാൽ, “../” കണ്ടുമുട്ടുമ്പോഴെല്ലാം, നിലവിലെ ഫോൾഡറിൽ നിന്ന് പുറത്തുവരണം (അതായത് പാരന്റ് ഫോൾഡറിലേക്ക് നീങ്ങുക), നിലവിലെ ഫോൾഡർ റൂട്ട് ആണോ എന്ന് പരിശോധിക്കും. ഇല്ലെങ്കിൽ, മുകളിലെ ഘടകം ഞങ്ങൾ സ്റ്റാക്കിൽ നിന്ന് പോപ്പ് ചെയ്യും.
തീർച്ചയായും ഒരു “./” നേരിടുമ്പോഴെല്ലാം ഞങ്ങൾ ഒന്നും ചെയ്യേണ്ടതില്ല.
ഈ മൂന്ന് കേസുകളും ഞങ്ങൾ കൈകാര്യം ചെയ്യുന്നത് മറ്റെന്തെങ്കിലും ആണെങ്കിൽ.

ഇവിടെ നമ്മൾ അറിഞ്ഞിരിക്കേണ്ട ഒരു കാര്യം, സ്റ്റാക്കിലുള്ള മൂലകങ്ങളുടെ എണ്ണം, റൂട്ട് ഫോൾഡറിൽ നിന്ന് നിലവിൽ ഏത് ആഴത്തിലാണ് എന്ന് പറയുന്നു.
അങ്ങനെ, ഞങ്ങൾ സ്റ്റാക്കിന്റെ വലുപ്പം അവസാനം നൽകും, അതായത് റൂട്ട് ഫോൾഡറിൽ നിന്നുള്ള ഡെപ്ത്.

ക്രാളർ ലോഗ് ഫോൾഡർ ലീറ്റ്കോഡ് പരിഹാരത്തിനുള്ള നടപ്പാക്കൽ

സി ++ പ്രോഗ്രാം

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int minOperations(vector<string>& logs) {
        stack<string>stack;
        for(string log:logs){
            if(log=="../"){
                if(stack.size()>0)stack.pop();
            }
            else if(log=="./");
            else{
                stack.push(log);
            }
        }
        return stack.size();
    }
int main()
{
    vector<string>logs{"d1/","d2/","../","d21/","./"};
    cout<<minOperations(logs);
}
2

ജാവ പ്രോഗ്രാം

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

class Solution
{  
    public static int minOperations(String[] logs) {
        Stack<String>stack=new Stack<String>();
        for(String log:logs){
            if(log.equals("../")){
                if(stack.size()>0)stack.pop();
            }
            else if(log.equals("./"));
            else{
                stack.push(log);
            }
        }
        return stack.size();
    }
    
    public static void main(String args[])
    {
        String[]logs={"d1/","d2/","../","d21/","./"};
        
        System.out.println(minOperations(logs));
    }
}
2

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

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

O (n): തന്നിരിക്കുന്ന സ്ട്രിംഗുകളുടെ ശ്രേണി ഞങ്ങൾ രേഖീയമായി സഞ്ചരിക്കുകയും ഓരോ ആവർത്തനത്തിലും O (1) സമയത്തിൽ സ്റ്റാക്ക് പ്രവർത്തനം നടത്തുകയും ചെയ്യുന്നു. അതിനാൽ, സമയ സങ്കീർണ്ണത O (n) ആണ്, ഇവിടെ n എന്നത് ഇൻപുട്ട് അറേയുടെ നീളം.

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

O (n): നൽകിയ ഇൻപുട്ട് അറേ ദൈർഘ്യത്തിന് തുല്യമാകാവുന്ന ഒരു സ്റ്റാക്ക് ഞങ്ങൾ ഉപയോഗിച്ചു. അങ്ങനെ, ഏറ്റവും മോശം സ്ഥല സങ്കീർണ്ണത O (n) ആണ്.

സമീപനം 2 (ഡെപ്ത് വേരിയബിൾ ഉപയോഗിക്കുന്നു)

ഡെപ്ത് വേരിയബിൾ ട്രാക്കുചെയ്യുന്നത് തുടരുന്നതിലൂടെ പ്രശ്നം എളുപ്പത്തിൽ പരിഹരിക്കാനാകും, ഇത് അടിസ്ഥാനപരമായി റൂട്ട് ഫോൾഡറിൽ നിന്ന് ഞങ്ങൾ ഏത് ആഴത്തിലാണ് എന്ന് കാണിക്കുന്നു.
ഓരോ തവണയും ഞങ്ങൾ ഒരു ചൈൽഡ് ഫോൾഡറിലേക്ക് പോകുമ്പോൾ, റൂട്ട് ഫോൾഡറിൽ നിന്ന് ദൂരം 1 വരെ പോകുന്നു. (അതായത് ഡെപ്ത് ++)
ഓരോ തവണയും ഞങ്ങൾ ഒരു രക്ഷാകർതൃ ഫോൾഡറിലേക്ക് പോകുമ്പോൾ, റൂട്ട് ഫോൾഡറിനടുത്തുള്ള ദൂരം 1 ആയി കുറയുന്നു.
ഞങ്ങൾ റൂട്ട് ഫോൾഡറിൽ ഇല്ലെങ്കിൽ മാത്രമേ നമുക്ക് രക്ഷാകർതൃ ഫോൾഡറിലേക്ക് പോകാൻ കഴിയൂ എന്നത് ശ്രദ്ധിക്കുക.
അതിനാൽ, ഫോർ ഫോർ ഇടത്തുനിന്ന് വലത്തോട്ട് കമാൻഡുകൾ എക്സിക്യൂട്ട് ചെയ്യാൻ ഞങ്ങൾ ആരംഭിക്കും ലൂപ്പ് .

  • “../” കണ്ടുമുട്ടിയാൽ നമ്മൾ റൂട്ട് ഫോൾഡറിലാണോ അല്ലയോ എന്ന് പരിശോധിക്കും. ഇല്ലെങ്കിൽ ഞങ്ങൾ ഡെപ്ത് 1 കുറയ്ക്കും.
  • അല്ലാത്തപക്ഷം “./” കണ്ടുമുട്ടിയാൽ നമുക്ക് നിലവിലെ ഫോൾഡറിൽ തന്നെ തുടരേണ്ടിവരും, അതിനാൽ ഡെപ്ത് വേരിയബിളിൽ മാറ്റമില്ല.
  • അല്ലെങ്കിൽ ഞങ്ങളുടെ ഒരു ചൈൽഡ് ഫോൾഡറിലേക്ക് മാറണം. അങ്ങനെ, നമ്മുടെ ആഴം 1 വർദ്ധിപ്പിക്കും.

എല്ലാ കമാൻഡുകൾക്കും ശേഷം, റൂട്ട് ഫോൾഡറിൽ നിന്നുള്ള ദൂരം സംഭരിക്കുകയാണ് ഞങ്ങളുടെ ഡെപ്ത് വേരിയബിൾ. ഞങ്ങൾ അത് .ട്ട്‌പുട്ടായി നൽകും.

ക്രാളർ ലോഗ് ഫോൾഡർ ലീറ്റ്കോഡ് പരിഹാരത്തിനുള്ള നടപ്പാക്കൽ

സി ++ പ്രോഗ്രാം

#include <iostream>
#include <vector>
using namespace std;

int minOperations(vector<string>& logs)
{
    int depth=0;
    for(string log:logs)
    {
        if(log=="../")
        {
            if(depth>0)depth--;//moving to parent folder only if depth>0 i.e. current folder is    
                                 other than main folder 
        }
        else if(log=="./");    //staying to current folder
        else depth++;          //moving to child folder
    }
    return depth;
}
int main()
{
    vector<string>logs{"d1/","d2/","../","d21/","./"};
    cout<<minOperations(logs);
}
2

ക്രാളർ ലോഗ് ഫോൾഡർ ലീറ്റ്കോഡ് പരിഹാരത്തിനായുള്ള ജാവ പ്രോഗ്രാം

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

class Solution
{  
    public static int minOperations(String[] logs)
    {
        int depth=0;
        for(String log:logs)
        {
            if(log.equals("../"))
            {
                if(depth>0)depth--;//moving to parent folder only if depth>0 i.e. current folder is other than main folder 
            }
            else if(log.equals("./"));  //staying to current folder
            else depth++;               //moving to child folder
        }
        return depth;
    }
    
    public static void main(String args[])
    {
        String[]logs={"d1/","d2/","../","d21/","./"};
        
        System.out.println(minOperations(logs));
    }
}
2

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

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

O (n): ഞങ്ങൾ എല്ലാ കമാൻഡുകളും ഒരു തവണ എക്സിക്യൂട്ട് ചെയ്യുന്നു. അതിനാൽ, സമയ സങ്കീർണ്ണത O (n) ആണ്.

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

O (1): ഞങ്ങൾ ഒരു ഡെപ്ത് വേരിയബിൾ ഉപയോഗിച്ചു. അതിനാൽ, സ്ഥല സങ്കീർണ്ണത O (1) ആണ്.