मान लीजिए कि हमारे पास तीन तार s1, s2, और s3 हैं, हमें उनके सबसे लंबे सामान्य अनुक्रम की लंबाई ज्ञात करनी है।
इसलिए, यदि इनपुट s1 ="ababchemxde" s2 ="pyakcimde" s3 ="oauctime" जैसा है, तो आउटपुट 4 होगा, क्योंकि सबसे लंबा सामान्य क्रम "acme" है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- m:=s1 का आकार, n:=s2 का आकार, o:=s3 का आकार
- dp :=आकार का एक 3D मैट्रिक्स (o + 1) x (n + 1) x (m + 1)
- 1 से मी की सीमा में i के लिए, करें
- जे के लिए 1 से n तक, करें
- k श्रेणी 1 से o के लिए, करें
- यदि s1[i-1], s2[j-1], s3[k-1] समान हैं, तो
- dp[i, j, k] :=1 + dp[i-1, j-1, k-1]
- अन्यथा,
- dp[i, j, k] =अधिकतम (dp[i - 1, j, k], dp[i, j-1, k] और dp[i,j, k-1])ली>
- यदि s1[i-1], s2[j-1], s3[k-1] समान हैं, तो
- k श्रेणी 1 से o के लिए, करें
- जे के लिए 1 से n तक, करें
- रिटर्न डीपी[एम, एन, ओ]
उदाहरण (पायथन)
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
class Solution: def solve(self, s1, s2, s3): m = len(s1) n = len(s2) o = len(s3) dp = [[[0 for i in range(o + 1)] for j in range(n + 1)] for k in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): for k in range(1, o + 1): if s1[i - 1] == s2[j - 1] == s3[k - 1]: dp[i][j][k] = 1 + dp[i - 1][j - 1][k - 1] else: dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j - 1][k], dp[i][j][k - 1]) return dp[m][n][o] ob = Solution() s1 = "ababchemxde" s2 = "pyakcimde" s3 = "oauctime" print(ob.solve(s1, s2, s3))
इनपुट
"ababchemxde", "pyakcimde", "oauctime"
आउटपुट
4