পাইথনে লংগেস্ট ডিমিনিশিং ওয়ার্ড চেইন (শব্দ শৃঙ্খল) দৈর্ঘ্য বের করা

সমস্যা বিবরণ

একটি বৈধ শব্দের লিস্ট words এবং একটি স্ট্রিং s দেওয়া আছে। s থেকে শুরু করে একবারে একটি অক্ষর কাটিয়ে যাওয়ায় যতক্ষণ সম্ভব বৈধ শব্দ বানানো যায়, সেটির সর্বোচ্চ দৈর্ঘ্য (চেইন লেন্থ) বের করতে হবে।

উদাহরণ

words = ["lii", "limit", "limi", "li", "coffee", "jug", "pool", "type"]
s = "limit"

চেইন: "limit" → "limi" → "lii" → "li"
Output: 4

অ্যালগরিদম: রিকার্সিভ + মেমোইজেশন (DP on Strings)

1. words কে সেটে কনভার্ট করুন O(1) লুকআপের জন্য
2. dfs(current_word) ফাংশন:
   • যদি মেমোতে থাকে → রিটার্ন
   • max_len = 1 (ন্যূনতম নিজে)
   • প্রতিটি পজিশন j এর জন্য অক্ষর কাটিয়ে next_word বানান
   • যদি next_word in word_set হলে:
     • max_len = max(max_len, 1 + dfs(next_word))
   • মেমোতে সংরক্ষণ করুন এবং রিটার্ন

পাইথন কোড

class Solution:
    def solve(self, words, s):
        word_set = set(words)
        memo = {}
        
        def dfs(word):
            if word in memo:
                return memo[word]
            
            max_len = 1  # ন্যূনতম নিজের দৈর্ঘ্য
            for j in range(len(word)):
                next_word = word[:j] + word[j+1:]
                if next_word in word_set:
                    max_len = max(max_len, 1 + dfs(next_word))
            
            memo[word] = max_len
            return max_len
        
        return dfs(s) if s in word_set else 0

ob = Solution()
words = ["lii", "limit", "limi", "li", "coffee", "jug", "pool", "type"]
s = "limit"
print(ob.solve(words, s))  # 4

প্রদত্ত কোডের সমস্যা ও সমাধান

প্রদত্ত কোডে for i in words লুপ আছে যা অপ্রয়োজনীয় এবং বগ-prone। সরাসরি s in word_set চেক করাই যথেষ্ট।

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(N × L²) — N = শব্দ সংখ্যা, L = গড় দৈর্ঘ্য (প্রতিটি শব্দে L সাবস্ট্রিং)
• স্থান জটিলতা: O(N × L) — মেমো + সেট

উপসংহার

• সেট + মেমোইজেশন দিয়ে ডিপি অন স্ট্রিংস
• প্রতিটি শব্দ একবারই প্রসেস হয়
• গ্রাফ হিসেবে মডেল করলে (নোড=শব্দ, এজ=এক অক্ষর কাটা) লংগেস্ট পাথ = DP on DAG