Chuỗi con riêng biệt trong C ++

Giả sử chúng ta có các chuỗi S và T. Chúng ta phải đếm số chuỗi phân biệt của S bằng T.

Chúng ta biết rằng một chuỗi con của một chuỗi là một chuỗi mới được hình thành từ chuỗi ban đầu bằng cách loại bỏ một số ký tự (có thể không có) mà không làm ảnh hưởng đến vị trí tương đối của các ký tự còn lại. (Giống như, "ACE" là một dãy con của "ABCDE" trong khi "AEC" thì không).

Nếu các chuỗi đầu vào là “baalllloonnn” và “bong bóng”, thì sẽ có 36 cách khác nhau để chọn.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của s, m:=kích thước của t. Cập nhật s và t bằng cách nối các khoảng trắng trước chúng

• Tạo một ma trận có kích thước (n + 1) x (m + 1)

• đặt dp [0, 0]:=1, sau đó đặt 1 cho cột thứ 0 của tất cả hàng, đặt 1

• cho tôi trong phạm vi từ 1 đến n

  • đối với j trong phạm vi từ 1 đến m

    • nếu s [i] =t [j] thì

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

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

• trả về dp [n, m]

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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"));
}

Đầu vào

"baalllloonnn"
"balloon"

Đầu ra

36