algorithm
दूरस्थ डायनामिक एल्गोरिदम संपादित करें
खोज…
स्ट्रिंग 1 को स्ट्रिंग 2 में बदलने के लिए न्यूनतम संपादन आवश्यक है
समस्या कथन यह है कि यदि हमें दो स्ट्रिंग str1 और str2 दिए जाते हैं तो str1 पर कितने न्यूनतम ऑपरेशन किए जा सकते हैं जो कि str2 में परिवर्तित हो जाते हैं। ऑपरेशन हो सकते हैं:
- सम्मिलित करें
- हटाना
- बदलने के
उदाहरण के लिए
Input: str1 = "geek", str2 = "gesek"
Output: 1
We only need to insert s in first string
Input: str1 = "march", str2 = "cart"
Output: 3
We need to replace m with c and remove character c and then replace h with t
इस समस्या को हल करने के लिए हम एक 2 डी सरणी डीपी [एन + 1] [एम + 1] का उपयोग करेंगे जहां एन पहले स्ट्रिंग की लंबाई है और एम दूसरे स्ट्रिंग की लंबाई है। हमारे उदाहरण के लिए, यदि str1 azcef है और str2 है abcdef तो हमारे सरणी डीपी हो जाएगा [6] [7] और हमारे अंतिम जवाब डीपी [5] में संग्रहीत किया जाएगा। [6]
(a) (b) (c) (d) (e) (f)
+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+---+---+---+---+---+---+---+
(a)| 1 | | | | | | |
+---+---+---+---+---+---+---+
(z)| 2 | | | | | | |
+---+---+---+---+---+---+---+
(c)| 3 | | | | | | |
+---+---+---+---+---+---+---+
(e)| 4 | | | | | | |
+---+---+---+---+---+---+---+
(f)| 5 | | | | | | |
+---+---+---+---+---+---+---+
डी पी के लिए [1] [1] हमारे पास जांच करने के लिए है कि हम क्या हो जाएगा एक यह में एक कन्वर्ट करने के लिए क्या कर सकते हैं 0 .For डी पी [1] [2] हम क्या हम अब यह में एक कन्वर्ट करने के लिए कर सकते हैं की जाँच करने के लिए है 1 होगा क्योंकि हमें b डालना है। 1 पुनरावृत्ति के बाद हमारा एरे जैसा दिखेगा
(a) (b) (c) (d) (e) (f)
+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+---+---+---+---+---+---+---+
(a)| 1 | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
(z)| 2 | | | | | | |
+---+---+---+---+---+---+---+
(c)| 3 | | | | | | |
+---+---+---+---+---+---+---+
(e)| 4 | | | | | | |
+---+---+---+---+---+---+---+
(f)| 5 | | | | | | |
+---+---+---+---+---+---+---+
पुनरावृति के लिए २
डी पी के लिए [2] [1] हम चाहते हैं कि जांच करने के लिए एक हम डी पी [2] [2] के लिए z दूर करने के लिए है, इसलिए डीपी [2] [1] 1 हो जाएगा .Similary जरूरत के लिए az कन्वर्ट करने के लिए है हम जेड प्रतिस्थापित करने की आवश्यकता b के साथ, इसलिए dp [2] [2] १ होगा। २ पुनरावृति के बाद हमारा dp [] एरे जैसा दिखेगा।
(a) (b) (c) (d) (e) (f)
+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+---+---+---+---+---+---+---+
(a)| 1 | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
(z)| 2 | 1 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
(c)| 3 | | | | | | |
+---+---+---+---+---+---+---+
(e)| 4 | | | | | | |
+---+---+---+---+---+---+---+
(f)| 5 | | | | | | |
+---+---+---+---+---+---+---+
तो हमारा सूत्र दिखेगा
if characters are same
dp[i][j] = dp[i-1][j-1];
else
dp[i][j] = 1 + Min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
अंतिम पुनरावृत्ति के बाद हमारा dp [] एरे जैसा दिखेगा
(a) (b) (c) (d) (e) (f)
+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+---+---+---+---+---+---+---+
(a)| 1 | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
(z)| 2 | 1 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
(c)| 3 | 2 | 2 | 1 | 2 | 3 | 4 |
+---+---+---+---+---+---+---+
(e)| 4 | 3 | 3 | 2 | 2 | 2 | 3 |
+---+---+---+---+---+---+---+
(f)| 5 | 4 | 4 | 2 | 3 | 3 | 3 |
+---+---+---+---+---+---+---+
जावा में कार्यान्वयन
public int getMinConversions(String str1, String str2){
int dp[][] = new int[str1.length()+1][str2.length()+1];
for(int i=0;i<=str1.length();i++){
for(int j=0;j<=str2.length();j++){
if(i==0)
dp[i][j] = j;
else if(j==0)
dp[i][j] = i;
else if(str1.charAt(i-1) == str2.charAt(j-1))
dp[i][j] = dp[i-1][j-1];
else{
dp[i][j] = 1 + Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1]));
}
}
}
return dp[str1.length()][str2.length()];
}
समय जटिलता
O(n^2)