ওয়ার্ড চেইন
মনে করুন word1 হলো word2-এর প্রিডিসেসর (predecessor) যদি এবং কেবল যদি আমরা word1-এ ঠিক একটি অক্ষর যেকোনো জায়গায় যোগ করে সেটি word2-এর সমান করতে পারি। উদাহরণস্বরূপ, "abc" হলো "abac"-এর প্রিডিসেসর।
একটি ওয়ার্ড চেইন হলো শব্দের একটি সিকোয়েন্স [word_1, word_2, ..., word_k] যেখানে k >= 1, word_1 হলো word_2-এর প্রিডিসেসর, word_2 হলো word_3-এর প্রিডিসেসর, ইত্যাদি।
সমস্যা
আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা একটি স্ট্রিং অ্যারে arr প্রথম ও একমাত্র আর্গুমেন্ট হিসেবে নেবে।
অ্যারে arr-এর প্রতিটি স্ট্রিং ইংরেজি লোয়ারকেস অক্ষর দিয়ে গঠিত। আমাদের ফাংশনটি দেওয়া অ্যারে থেকে বেছে নেওয়া শব্দগুলো দিয়ে সম্ভব সবচেয়ে দীর্ঘ ওয়ার্ড চেইনের দৈর্ঘ্য রিটার্ন করবে।
উদাহরণস্বরূপ, যদি ফাংশনে ইনপুট হয়:
const arr = ["a","b","ba","bca","bda","bdca"];
তাহলে আউটপুট হবে:
const output = 4;
আউটপুট ব্যাখ্যা:
সর্বোচ্চ দীর্ঘ ওয়ার্ড চেইনগুলোতে একটি হলো "a","ba","bda","bdca"।
উদাহরণ
এই সমস্যার কোড:
const arr = ["a","b","ba","bca","bda","bdca"];
const longestStrChain = (arr) => {
arr.sort((a, b) => a.length - b.length);
const isPredecessor = (word1 = '', word2 = '') => {
if(Math.abs(word1.length - word2.length) !== 1){
return false;
};
for(let i = 0; i < word2.length; i++){
const word = word2.slice(0, i) + word2.slice(i + 1);
if(word === word1){
return true;
};
};
return false;
};
const array = [];
let max = 0;
for(let i = arr.length - 1; i >= 0; i--){
array[i] = 1;
for(let j = arr.length - 1; j > i; j--){
if(isPredecessor(arr[i], arr[j])){
array[i] = Math.max(
array[i],
1 + array[j],
);
};
};
max = Math.max(max, array[i]);
};
return max;
};
console.log(longestStrChain(arr));
আউটপুট
কনসোলে আউটপুট:
4
