home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Subsequences ที่แตกต่างกันใน C++

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

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

ถ้าสตริงอินพุตคือ "baalllloonnn" และ "balloon" จะมี 36 วิธีที่แตกต่างกันในการเลือก

ขั้นตอนการแก้ปัญหา

  • n := ขนาดของ s, m := ขนาดของ t อัปเดต s และ t โดยต่อเว้นวรรคหน้าสตริง
  • สร้างเมทริกซ์ขนาด (n + 1) x (m + 1)
  • ตั้งค่า dp[0, 0] := 1 จากนั้นตั้งค่า 1 ให้คอลัมน์ที่ 0 ของทุกแถว
  • for i ในช่วง 1 ถึง n
    • for 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]

ตัวอย่างโค้ด C++

#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];
    }
};

int main(){
    Solution ob;
    cout << (ob.numDistinct("baalllloonnn", "balloon"));
}

อินพุต

"baalllloonnn" "balloon"

เอาต์พุต

36