మార్గం క్రాసింగ్ లీట్‌కోడ్ పరిష్కారం


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అమెజాన్
హ్యాషింగ్ స్ట్రింగ్

సమస్యల నివేదిక

పాత్ క్రాసింగ్ సమస్యలో a_ స్ట్రింగ్ 1 యూనిట్ ద్వారా ఒక సమయంలో ఒక దిశలో ఒక వస్తువు యొక్క కదలికను చూపించే 'N', 'S', 'E' లేదా 'W' అనే నాలుగు వేర్వేరు అక్షరాలు మాత్రమే ఇవ్వబడ్డాయి. ఆబ్జెక్ట్ మొదట్లో మూలం (0,0). ఇచ్చిన స్ట్రింగ్‌లో పేర్కొన్న మార్గంలో ఏ సమయంలోనైనా వస్తువు దాని మార్గాన్ని దాటుతుందో లేదో మనం కనుగొనాలి.

ఉదాహరణ

path = "NES"
false

వివరణ:

మార్గం క్రాసింగ్ లీట్‌కోడ్ పరిష్కారం

మార్గం ఒకటి కంటే ఎక్కువసార్లు ఏ పాయింట్‌ను దాటదని గమనించండి.

path = "NESWW"
true

వివరణ:

మార్గం క్రాసింగ్ లీట్‌కోడ్ పరిష్కారం

మార్గం మూలాన్ని రెండుసార్లు సందర్శిస్తుందని గమనించండి.

అప్రోచ్

సమస్య స్టేట్మెంట్ నుండి ఒక కోఆర్డినేట్ (x, y) వస్తువు యొక్క మార్గంలో సంభవిస్తే, అది ప్రతిసారీ 1 యూనిట్తో కదులుతున్నప్పుడు అది నిర్దిష్ట సంఖ్యలో కదలికల తరువాత వస్తువు యొక్క స్థానం అయి ఉండాలి.
ఇంతకుముందు సందర్శించిన దాని మార్గంలో ఒక పాయింట్ వస్తే, అది ఖచ్చితంగా మార్గాన్ని దాటుతుంది. కాబట్టి మేము ఈ రకమైన పాయింట్ కనుగొన్న వెంటనే నిజం తిరిగి రావచ్చు.

ఇంతకుముందు ఒక పాయింట్ సందర్శించబడిందని ఇప్పుడు మనకు ఎలా తెలుసు. దీని కోసం మనం a హాష్ సెట్ మరియు అన్ని పాయింట్లను దాని మార్గంలో నిల్వ ఉంచండి. ఏ సమయంలోనైనా తదుపరి వస్తువు సెట్‌లోకి వెళుతోందని మేము కనుగొంటే, మేము నిజం అవుతాము. ఇది జరగకపోతే మార్గం పూర్తి చేసిన తరువాత, మేము తప్పుడు తిరిగి ఇస్తాము.

అల్గోరిథం:

  1. కీ సమన్వయ (x, y) ను సూచించే కీల హాష్ సెట్‌ను సృష్టించండి. దీని కోసం మనం జతను ఉపయోగించవచ్చు కీగా లేదా మేము రెండు పూర్ణాంకాలను ప్రత్యేకంగా సూచించే సాధారణ స్ట్రింగ్‌ను ఉపయోగించవచ్చు. Ex- కోఆర్డినేట్ (2) ను సూచించడానికి “3_2,3”.
  2. X మరియు y అనే రెండు వేరియబుల్ సృష్టించండి. మూలం కోఆర్డినేట్ (0,0) తో వాటిని ప్రారంభించండి మరియు దాన్ని సెట్‌లో చొప్పించండి.
  3. పేర్కొన్న కదలికలను మళ్ళించడానికి లూప్‌ను అమలు చేయండి. ప్రస్తుత కదలిక ప్రకారం x లేదా y విలువను ఈ క్రింది విధంగా పెంచడం లేదా తగ్గించడం:
    'N' అంటే కొత్త కోఆర్డినేట్ (x, y + 1)
    'E' అంటే కొత్త కోఆర్డినేట్ (x + 1, y)
    'S' అంటే కొత్త కోఆర్డినేట్ (x, y-1)
    'W' అంటే కొత్త కోఆర్డినేట్ (x-1, y)
  4. సమన్వయం (x, y) సెట్‌లో ఉందో లేదో తనిఖీ చేయండి. ఉన్నట్లయితే నిజం తిరిగి, లేకపోతే ఈ కోఆర్డినేట్‌ను సెట్‌లోకి జోడించి కొనసాగించండి.
  5. క్రాసింగ్ కనుగొనబడకపోతే లూప్ పూర్తయిన తర్వాత తిరిగి తప్పు.

అమలు

పాత్ క్రాసింగ్ లీట్‌కోడ్ సొల్యూషన్ కోసం సి ++ ప్రోగ్రామ్

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

bool isPathCrossing(string path) 
{
    set< pair<int,int> > s;
    int x=0,y=0;
    s.insert({x,y});

    for(char c: path)
    {
        if(c=='N') y++;
        if(c=='E') x++;
        if(c=='S')  y--;
        if(c=='W')  x--;

        if(s.count({x,y}))
        return true;

        s.insert({x,y});
    }

    return false;
}

int main() 
{
    string path = "NESWW";
    if(isPathCrossing(path))
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;

  return 0; 
}
true

పాత్ క్రాసింగ్ లీట్‌కోడ్ సొల్యూషన్ కోసం జావా ప్రోగ్రామ్

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

class PathCrossing
{  
    public static boolean isPathCrossing(String path) 
    {
        Set<String> set=new HashSet<String>();

        int x=0,y=0;
        String key= x + "_" + y;

        set.add(key);

        for(int i=0;i<path.length();i++)
        {
            char c= path.charAt(i);
            if(c=='N') y++;
            if(c=='E') x++;
            if(c=='S') y--;
            if(c=='W') x--;

            key= x + "_" + y;
            if(set.contains(key)) return true;

            set.add(key);
        }

        return false;
    }
    
    public static void main(String args[])
    {
       String path = "NESWW";
  
       System.out.println(isPathCrossing(path));
        
    }
}
true

పాత్ క్రాసింగ్ లీట్‌కోడ్ సొల్యూషన్ కోసం సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై) : ఇక్కడ N అనేది ఇచ్చిన స్ట్రింగ్ యొక్క పరిమాణం. మేము స్ట్రింగ్‌లోని ప్రతి అక్షరాన్ని ఒక్కసారి మాత్రమే సందర్శించినప్పుడు, సమయ సంక్లిష్టత O (N).

అంతరిక్ష సంక్లిష్టత 

పై) : సందర్శించిన కోఆర్డినేట్‌లను సమితిలో నిల్వ చేయడానికి మేము ఉపయోగిస్తున్న అదనపు మెమరీ.