Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में Minimum ASCII Delete Sum for Two Strings


मान लीजिए हमारे पास दो शब्द w1 और w2 हैं, हमें हटाए गए वर्णों का न्यूनतम ASCII योग खोजना है ताकि w1 और w2 समान हो जाएं, जहां प्रत्येक चरण में हम किसी भी स्ट्रिंग में एक वर्ण हटा सकते हैं। इसलिए यदि इनपुट "sea" और "eat" जैसा है, तो आउटपुट 231 होगा, क्योंकि हमें w1 से 's' हटाना होगा, यह "ea" हो जाएगा और w2 से "eat" से "t" हटाना होगा। फिर वे समान हो जाएंगे। "eat" से 't' हटाने पर योग में 116 जुड़ जाता है, और अंत में, दोनों स्ट्रिंग्स समान होती हैं और 115 + 116 = 231 इसे प्राप्त करने के लिए न्यूनतम संभव योग है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

  • n := s1 का आकार, m := s2 का आकार
  • स्ट्रिंग्स s1 और s2 से पहले एक खाली स्थान जोड़ें, फिर s1 और s2 को तदनुसार अपडेट करें
  • (n + 1) x (m + 1) आकार की एक तालिका बनाएं
  • i := 1 से m तक
    • dp[0, i] := dp[0, i - 1] + s2[i]
  • i := 1 से n तक
    • dp[i, 0] := dp[i - 1, 0] + s1[i]
  • i को 1 से n तक की रेंज में
    • j को 1 से m तक की रेंज में
      • यदि s1[i] = s2[j]
        • dp[i, j] := dp[i - 1, j - 1]
      • अन्यथा dp[i, j] = dp[i - 1, j] + 1 और dp[i, j - 1] + 1 का न्यूनतम
  • dp[n, m] लौटाएं

उदाहरण (C++)

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h> using namespace std; class Solution { public:    int minimumDeleteSum(string s1, string s2) {       int n = s1.size();       int m = s2.size();       s1 = " " + s1;       s2 = " " + s2;       vector < vector <int> > dp(n + 1, vector <int>(m + 1));       for(int i = 1; i <= m; i++){          dp[0][i] = dp[0][i - 1] + s2[i];       }       for(int i = 1; i <= n; i++){          dp[i][0] = dp[i - 1][0] + s1[i];       }       for(int i = 1; i <= n; i++){          for(int j = 1; j <= m; j++){             if(s1[i] == s2[j]){                dp[i][j] = dp[i - 1][j - 1];             }             else{                dp[i][j] = min(dp[i - 1][j] + s1[i], dp[i][j - 1] + s2[j]);             }          }       }       return dp[n][m];    } }; main(){    Solution ob;    cout << (ob.minimumDeleteSum("sea", "eat")); }

इनपुट

"sea" "eat"

आउटपुट

231

  1. - C++ में दो बड़ी संख्याओं का योग

    इस समस्या में, हमें दो स्ट्रिंग दी गई हैं जो दो बड़ी संख्याओं को परिभाषित करती हैं। हमारा कार्य दो बड़ी संख्याओं का योग खोजने के लिए एक प्रोग्राम बनाना है। आइए एक उदाहरण लेते हैं समस्या को समझने के लिए, इनपुट: number1 = 341299123919 number2 = 52413424 आउटपुट: 341351537343 इस समस्या को हल करने के लिए

  1. - C++ में दो संख्याओं का मॉड्यूलो M योग

    इस समस्या में, हमें तीन संख्याएं a, b, और M दी गई हैं। हमारा कार्य एक प्रोग्राम बनाना है जो दो संख्याओं का मॉड्यूलो M योग निकाले।उदाहरण से समझते हैंइनपुट: a = 14, b = 54, m = 7 आउटपुट: 5 व्याख्या: 14 + 54 = 68, 68 % 7 = 5इस समस्या को हल करने के लिए, हम बस संख्याओं a और b को जोड़ेंगे। और फिर योग को M

  1. C++ में टू सम IV - इनपुट एक BST है C++ में टू सम IV - इनपुट एक BST है

    मान लीजिए हमारे पास एक बाइनरी सर्च ट्री और एक लक्ष्य मान है; हमें जांचना है कि क्या BST में दो तत्व मौजूद हैं जिनका योग दिए गए लक्ष्य के बराबर है या नहीं। इसलिए, यदि इनपुट जैसा है: तो आउटपुट True होगा। इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे: एक सरणी v परिभाषित करें एक फ़ंक्शन inor