পাথ ক্রসিং লেটকোড সমাধান  


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক
আলগোরিদিম আইনসংগ্রহ হ্যাশ সাক্ষাত্কার সাক্ষাৎকারের প্রস্তুতি লেটকোড LeetCodeSolutions স্ট্রিং

সমস্যা বিবৃতি  

পথ পারাপারের সমস্যায় a_string দেওয়া আছে যেখানে কেবলমাত্র চারটি পৃথক অক্ষর 'এন', 'এস', 'ই' বা 'ডাব্লু' রয়েছে যা একবারে 1 ইউনিট দ্বারা একটি বস্তুর গতিবেগ দেখায়। অবজেক্ট প্রাথমিকভাবে মূল (0,0) এ রয়েছে। আমাদের নির্ধারণ করতে হবে যে প্রদত্ত স্ট্রিংয়ে উল্লিখিত পথটি ধরে যে কোনও পয়েন্টে অবজেক্টটি তার পথটি অতিক্রম করবে কিনা।

উদাহরণ

path = "NES"
false

ব্যাখ্যা:

পাথ ক্রসিং লেটকোড সমাধান

লক্ষ্য করুন যে পথটি কোনও বিন্দু একাধিকবার অতিক্রম করবে না।

path = "NESWW"
true

ব্যাখ্যা:

পাথ ক্রসিং লেটকোড সমাধানপিন

লক্ষ্য করুন যে পথটি দু'বার উত্সকে দেখেছে।

অভিগমন  

সমস্যার বিবৃতি থেকে এটি স্পষ্ট যে যদি কোনও স্থানাঙ্কের (x, y) অবজেক্টের পথে ঘটে থাকে তবে অবশ্যই প্রতি বার 1 ইউনিট নিয়ে চলার কারণে নির্দিষ্ট সংখ্যক চলনের পরে এটি অবশ্যই অবজেক্টের অবস্থান হতে হবে।
সুতরাং যদি এমন কোনও বিন্দু যদি এর পথে আসে যা আগে একবার পরিদর্শন করা হয় তবে তা অবশ্যই পথটি অতিক্রম করবে। সুতরাং আমরা এই ধরণের পয়েন্টটি পাওয়া মাত্রই সত্যটিতে ফিরে আসতে পারি।

এখন আমরা কীভাবে জানি যে একটি বিন্দু আগে দেখা হয়েছিল। এই জন্য আমরা একটি ব্যবহার করতে পারেন হ্যাশ সেট এবং এর পথে সমস্ত পয়েন্ট সঞ্চিত রাখুন। যে কোনও সময়ে যদি আমরা দেখতে পেলাম যে পরবর্তী পয়েন্টটি কোন অবজেক্টে চলছে সেটির জন্য ইতিমধ্যে উপস্থিত রয়েছে, আমরা সত্যটিতে ফিরে আসছি। পথটি সম্পূর্ণ করার পরে যদি এটি না ঘটে, তবে আমরা মিথ্যা প্রত্যাবর্তন করব।

আরো দেখুন
ওয়াইল্ডকার্ডযুক্ত স্ট্রিং তুলনা

অ্যালগরিদম:

  1. কীগুলির একটি হ্যাশ সেট তৈরি করুন, যেখানে কী সমন্বয় (x, y) উপস্থাপন করে। এর জন্য আমরা জোড়া ব্যবহার করতে পারি কী হিসাবে বা আমরা একটি সাধারণ স্ট্রিং ব্যবহার করতে পারি যা পৃথকভাবে দুটি পূর্ণসংখ্যার উপস্থাপন করা উচিত। সমন্বিত প্রতিনিধিত্ব করার জন্য প্রাক্তন- "2_3" (২,৩)।
  2. এক্স এবং y দুটি ভেরিয়েবল তৈরি করুন। তাদের মূল সূচনা (0,0) দিয়ে সূচনা করুন এবং সেটটিতে এটি sertোকান।
  3. নির্দিষ্ট পদক্ষেপগুলি পুনরাবৃত্তি করার জন্য একটি লুপ চালান। বর্তমান পদক্ষেপ অনুযায়ী x বা y এর মান বৃদ্ধি বা হ্রাস:
    'এন' অর্থ নতুন স্থানাঙ্ক (x, y + 1)
    'ই' অর্থ নতুন স্থানাঙ্ক (x + 1, y)
    'এস' অর্থ নতুন স্থানাঙ্ক (x, y-1)
    'ডাব্লু' এর অর্থ নতুন স্থানাঙ্ক (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

পাথ ক্রসিং লেটকোড সমাধানের জন্য জটিলতা বিশ্লেষণ  

সময় জটিলতা

চালু) : যেখানে এন প্রদত্ত স্ট্রিংয়ের আকার। যেহেতু আমরা স্ট্রিংয়ের প্রতিটি অক্ষরকে কেবল একবারই দেখেছি, সুতরাং সময়ের জটিলতা হ'ল ও (এন)।

আরো দেখুন
সমস্ত অদ্ভুত দৈর্ঘ্যের সুবারারি লেটকোড সমাধানের যোগফল

স্পেস জটিলতা ity 

চালু) : অতিরিক্ত মেমরি আমরা একটি সেটে পরিদর্শন করা স্থানাঙ্কগুলি সঞ্চয় করতে ব্যবহার করছি।