ลำดับที่แตกต่างใน C ++

สมมติว่าเรามีสตริง S และ T เราต้องนับจำนวนลำดับที่แตกต่างกันของ S ซึ่งเท่ากับ T

เรารู้ว่าส่วนย่อยของสตริงเป็นสตริงใหม่ที่สร้างขึ้นจากสตริงดั้งเดิมโดยการลบอักขระบางตัว (ไม่สามารถเป็นได้) โดยไม่รบกวนตำแหน่งสัมพัทธ์ของอักขระที่เหลือ (เช่น "ACE" เป็นผลสืบเนื่องมาจาก "ABCDE" ในขณะที่ "AEC" ไม่ใช่)

หากสตริงอินพุตเป็น “baalllloonnn” และ “balloon” จะมี 36 วิธีในการเลือก

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ s , m :=ขนาดของ t อัปเดต s และ t โดยการต่อช่องว่างก่อนหน้านั้น

• สร้างเมทริกซ์ขนาดหนึ่ง (n + 1) x (m + 1)

• set dp[0, 0] :=1 จากนั้นตั้งค่า 1 สำหรับคอลัมน์ที่ 0 ของแถวทั้งหมด ใส่ 1

• สำหรับฉันอยู่ในช่วง 1 ถึง n

  • สำหรับ j ในช่วง 1 ถึง m

    • ถ้า s[i] =t[j] แล้ว

      • dp[i, j] :=dp[i – 1, j – 1]

    • dp[i, j] :=dp[i, j] + dp[i – 1, j]

• กลับ dp[n, m]

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   int numDistinct(string s, string t) {
      int n = s.size();
      int m = t.size();
      s = " " + s;
      t = " " + t;
      vector < vector <lli>> dp(n + 1, vector <lli> (m + 1));
      dp[0][0] = 1;
      for(int i = 1; i<= n; i++)dp[i][0] = 1;
      for(int i = 1; i <= n; i++){
         for(int j = 1; j <= m; j++){
            if(s[i] == t[j]) dp[i][j] = dp[i - 1][j - 1];
            dp[i][j]+= dp[i - 1][j];
         }
      }
      return dp[n][m];
   }
};
main(){
   Solution ob;
   cout << (ob.numDistinct("baalllloonnn", "balloon"));
}

อินพุต

"baalllloonnn"
"balloon"

ผลลัพธ์

36