Toph - See you again? Tutorial

 Problem Description here

এই প্রব্লেমটি আমার তৈরী করা একটি প্রব্লেম যেটি মূলত Intra CoU Programming Contest 2020 এর জন্য সেট করা। 

প্রব্লেমঃ প্রব্লেমটিতে বলা হয়েছে একটি n সাইজের ট্রি দেয়া থাকবে। যার প্রতিটি নোডে কিছু ক্যারেক্টার থাকবে। ট্রি এর রুট নোড হচ্ছে ১। বলতে হবে, এই ট্রি এর রুট থেকে লিফ পর্যন্ত এমন কোন পাথ আছে কি না যে পাথ "tareq&shawon" এই স্ট্রিং টা কে সাবসিকুয়েন্স হিসেবে ধারণ করে। যদি এমন পাথ থাকে তবে Lexicographically Smallest পাথটি প্রিন্ট করতে হবে। 

সল্যুশনঃ এই প্রব্লেমটির একটি ডিপি সল্যুশন সম্ভব। 

১) যেহেতু, Lexicographically Smallest পাথ বের করতে হবে তাই শুরুতেই প্রতিটি নোড এর জন্য তার এডজাসেন্সি লিস্ট টি Sort করে নিবো। 

২) ডিপি অ্যারের কাজ হবে প্রতিটি নোড থেকে লিফের দিকে যতোগুলো পাথ গেছে তাদের কোন একটি পাথ ধরে এখন পর্যন্ত স্ট্রিং এর যে ক্যারেক্টারগুলো সাবসিকুয়েন্স হিসেবে পেয়েছি সেগুলো ছাড়া বাকি সাফিক্সটুকু সাবসিকুয়েন্স হিসেবে পাওয়া যায় কি না সেটি ক্যালকুলেট করা। 

৩) এরপর, ডিপি অ্যারে ব্যাবহার করে ডিপি সল্যুশন প্রিন্ট করলেই কাজ শেষ! 


এরপরও না পারলে নিচের কোড দেখতে পারোঃ 

এই প্রব্লেমের আরো একটি সল্যুশন সম্ভব। তা ডিপি ছাড়াই করা যায় শুধু ডিএফএস দিয়ে। নিচে সেই কোডও দেয়া হলোঃ 

.

Happy Coding😀 

Comments

Trending Post

At Coder Educational DP-A | DP Series(Episode-1)

Magic In Grid

At Coder Educational DP-B | DP Series(Episode-2)