ট্রাই(Trie) হল 'Retrieval' ওয়ার্ড টার একটা Infix।কারণ ট্রাই ডিকশনারি থেকে একটা ওয়ার্ড কে শুধুমাত্র ওয়ার্ডটার একটা প্রিফিক্স দিয়েই খুঁজে বের করতে সক্ষম। Edward Fredkin প্রথমে 'Retrieval' শব্দের এই Infix নিয়ে এটাকে ট্রি(Tri) বলেন।কিন্তু গ্রাফ থিওরিতে ব্যাপকভাবে প্রচলিত 'ট্রি' থেকে আলাদা করার জন্যই এটাকে ট্রাই বলা হয়ে থাকে।
ট্রাই এর স্ট্রাকচার এবং কোড ইমপ্লিমেন্টেশন বুঝার জন্য শাফায়েত ভাইয়ের ব্লগ এর বিকল্প দেখি নাই।
ধরা যাক,একটা ডিকশনারিতে কতগুলো শব্দ দেয়া থাকবে,সেখান কতগুলো শব্দ কুয়েরি করে দেখতে হবে শব্দগুলো ডিকশনারিতে আছে কি না।এর জন্য স্যাম্পল কোড টা হলঃ
Printing Trie Lexicographically: Sample code
সতর্কতা(নিজের জন্য) ঃযে দুই টা ভুল প্রায়ই হয়!😑
১। প্রবলেমে টেস্টকেস থাকলে প্রতি টেস্টকেসেই নতুন ট্রাই ক্রিয়েট হচ্ছে কি না এবং আগের ট্রাই ধ্বংস হচ্ছে কি না ?দেখে নিতে হবে।
২। ট্রাই ডিলিট করার সময় next[] অ্যারের দিকে খেয়াল রাখা।
ট্রাই রিলেটেড প্রবলেম এবং সল্যুশনঃ
1. UVA-10226 (Hardwood Species)
Solution Idea: খুবই সহজ প্রবলেম।একটা ডাটাসেটে কতগুলো Hardwood Tree এর নাম দেয়া থাকবে।সেখান দেখতে হবে কোন Tree এর নামটা শতকরা কত ভাগ আছে।ট্রাই কে Traverse করে সব গুলো ইউনিক ট্রি প্রিন্ট করছি,সাথে সাথে শতকরা কত ভাগ আছে সেটাও প্রিন্ট করছি।
বিঃদ্রঃইনপুট নেয়ার ক্ষেত্রে সতর্ক থাকতে হবে।প্রতি ইনপুটের পূর্বেএকটা Blank Line হবে।
Solution: https://ideone.com/DfIsgA (See at your own risk👎).
2. LightOj 1129 (Consistency Checker)
Solution Idea: খুবই সহজ প্রবলেম।একটা ডাটাসেটে কতগুলো Hardwood Tree এর নাম দেয়া থাকবে।সেখান দেখতে হবে কোন Tree এর নামটা শতকরা কত ভাগ আছে।ট্রাই কে Traverse করে সব গুলো ইউনিক ট্রি প্রিন্ট করছি,সাথে সাথে শতকরা কত ভাগ আছে সেটাও প্রিন্ট করছি।
বিঃদ্রঃইনপুট নেয়ার ক্ষেত্রে সতর্ক থাকতে হবে।প্রতি ইনপুটের পূর্বেএকটা Blank Line হবে।
Solution: https://ideone.com/DfIsgA (See at your own risk👎).
2. LightOj 1129 (Consistency Checker)
Solution Idea: সব ফোন নাম্বার কে ট্রাইতে ইনসার্ট করার সাথে সাথে ভেক্টরে পুশ করে রাখছি।তারপর ভেক্টর এলিমেন্ট গুলো প্রতিটার জন্য ট্রাইতে সার্চ করে দেখছি,কোন একটা ফোন নাম্বার একবারের বেশি ট্রাইতে আছে কি না অথবা অন্য কোন ফোন নাম্বারের প্রিফিক্স হিসেবে আছে কি না।
Solution: https://ideone.com/ro93Rq (See at your own risk👎).
3. LightOj 1224 (DNA Prefix)
Solution Idea: n সংখ্যক DNA samples এর একটা সেট দেয়া থাকেবে।সেখান থেকে কতগুলো sample নিয়ে একটা সাবসেট করতে হবে যেন তাদের মধ্যকার longest common prefix*number of samples in the subset ম্যাক্সিমাম হয়। DNA samples যেহুতু শুধুমাত্র A,C,G,T দ্বারা গঠিত তাই এই চারটা ক্যারেক্টারকে যথাক্রমে 0,1,2,3 দিয়ে ম্যাপিং করে রেখে দিব।তাহলে চার লেন্থের একটা next[] অ্যারে ইউজ করলেই কাজ হয়ে যাবে।
Solution: https://ideone.com/5J1KcD (See at your own risk👎).
4. LightOj 1114 (Easily Readable)
Solution Idea: ডিকশনারিতে কতগুলো ওয়ার্ড দেয়া থাকবে,এবং কুয়েরি করার জন্য একটা সেনটেন্স থাকবে।এক্ষেত্রে আমরা যখন ওয়ার্ড গুলোকে ট্রাই তে ইনসার্ট করব,তখন ফার্স্ট এবং লাস্ট লেটার ছাড়া বাকি গুলোকে সর্ট করে ইনসার্ট করছি।কুয়েরি করার সময়ও সেনটেন্সের প্রতিটা ওয়ার্ডের ফার্স্ট এবং লাস্ট লেটার ছাড়া মিডলের গুলোকে সর্ট করে কুয়েরি করছি।
Solution: https://ideone.com/jXZqkh (See at your own risk👎).
3. LightOj 1224 (DNA Prefix)
Solution Idea: n সংখ্যক DNA samples এর একটা সেট দেয়া থাকেবে।সেখান থেকে কতগুলো sample নিয়ে একটা সাবসেট করতে হবে যেন তাদের মধ্যকার longest common prefix*number of samples in the subset ম্যাক্সিমাম হয়। DNA samples যেহুতু শুধুমাত্র A,C,G,T দ্বারা গঠিত তাই এই চারটা ক্যারেক্টারকে যথাক্রমে 0,1,2,3 দিয়ে ম্যাপিং করে রেখে দিব।তাহলে চার লেন্থের একটা next[] অ্যারে ইউজ করলেই কাজ হয়ে যাবে।
Solution: https://ideone.com/5J1KcD (See at your own risk👎).
4. LightOj 1114 (Easily Readable)
Solution Idea: ডিকশনারিতে কতগুলো ওয়ার্ড দেয়া থাকবে,এবং কুয়েরি করার জন্য একটা সেনটেন্স থাকবে।এক্ষেত্রে আমরা যখন ওয়ার্ড গুলোকে ট্রাই তে ইনসার্ট করব,তখন ফার্স্ট এবং লাস্ট লেটার ছাড়া বাকি গুলোকে সর্ট করে ইনসার্ট করছি।কুয়েরি করার সময়ও সেনটেন্সের প্রতিটা ওয়ার্ডের ফার্স্ট এবং লাস্ট লেটার ছাড়া মিডলের গুলোকে সর্ট করে কুয়েরি করছি।
Solution: https://ideone.com/jXZqkh (See at your own risk👎).
5. Hackerrank-Contacts
Solution Idea: ইনপুটে দুইটা কমান্ড আছে, কোন ওয়ার্ডের পূর্বে 'Add' কমান্ড থাকে সেই ওয়ার্ড টা ট্রাই তে ইনসার্ট করতে হবে আর 'Find' কমান্ড থাকলে খুঁজে বের করতে হবে ঐ প্রিফিক্স দিয়ে কয়টা ওয়ার্ড শুরু হয়েছে।
Solution: https://ideone.com/sjKI2l (See at your own risk👎).
6.Hackerrank-No Prefix Set
Solution Idea: এই প্রবলেমটা অনেকটা LightOj 1129 (Consistency Checker) এর মতই। কোন একটা সেট Consistent কি না চেক করতে হবে।
Solution: https://ideone.com/7izhgR (See at your own risk👎).
7. SPOJ DICT - Search in the dictionary!
Solution Idea: প্রতিটা কুয়েরি প্রিফিক্সের জন্য ট্রাই Traverse করছি।যদি প্রিফিক্সটা ট্রাই তে থাকে এবং তার চাইল্ড থাকে তাহলে ঐ প্রিফিক্স দিয়ে ট্রাই তে যত ওয়ার্ড আছে সেগুলো Lexicographically প্রিন্ট করছি,আর প্রিফিক্স ট্রাই তে না থাকলে বা আছে কিন্তু চাইল্ড নাই,সেক্ষেত্রে "No match."প্রিন্ট করছি।
Solution: https://ideone.com/AkFgDI (See at your own risk👎).
6.Hackerrank-No Prefix Set
Solution Idea: এই প্রবলেমটা অনেকটা LightOj 1129 (Consistency Checker) এর মতই। কোন একটা সেট Consistent কি না চেক করতে হবে।
Solution: https://ideone.com/7izhgR (See at your own risk👎).
7. SPOJ DICT - Search in the dictionary!
Solution Idea: প্রতিটা কুয়েরি প্রিফিক্সের জন্য ট্রাই Traverse করছি।যদি প্রিফিক্সটা ট্রাই তে থাকে এবং তার চাইল্ড থাকে তাহলে ঐ প্রিফিক্স দিয়ে ট্রাই তে যত ওয়ার্ড আছে সেগুলো Lexicographically প্রিন্ট করছি,আর প্রিফিক্স ট্রাই তে না থাকলে বা আছে কিন্তু চাইল্ড নাই,সেক্ষেত্রে "No match."প্রিন্ট করছি।
Solution: https://ideone.com/AkFgDI (See at your own risk👎).
No comments:
Post a Comment