資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學包含母音的最長公共子序列長度
在這個問題中，我們的任務是找到兩個字串中存在的最長公共子序列的長度，條件是子序列的每個字母都必須是母音。藉助遞迴演算法和迭代演算法，可以解決給定的問題陳述。在英文字母表中，存在五個母音字母：“A”、“E”、“I”、“O”、“U”。子序列與子串：在子序列中，我們可以以非連續的方式取字元，但在子串中，我們只能取連續的字元。
例如：在字串“TutorialsPoint”中：“tri”是子序列，但不是子串。而“tor”既是子序列又是子串。
舉幾個例子
示例1
字串1：“point”
字串2：“tutorials”
包含母音的公共子序列長度：2
示例2
字串1：“longestsub”
字串2：“ohbekhfuo”
包含母音的公共子序列長度：3
遞迴子結構
If idx_1 = 0 or idx_2 = 0, Then LCSVowels(idx1, idx2) = 0 Else If str1[idx_1-1] = str2[idx_2-1] and str1[idx_1-1] = Vowel, Then LCSVowels(idx_1, idx_2) = 1 + LCSVowels(idx_1-1, idx_2-1) Else LCSVowels(idx_1, idx_2) = max(LCSVowels(idx_1, idx_2-1), LCSVowels(idx_1-1, idx_2))
多種方法
我們提供了多種方法的解決方案。
迭代演算法。
遞迴演算法。
方法1：迭代演算法
這是一種基於迭代演算法的動態規劃方法。
演算法：LCSVowels(string1, string2)
步驟1：length1 = LENGTH(string1)
步驟2：length2 = LENGTH(string2)
步驟3：建立一個大小為(length1+1) X (length2+1)的二維整數陣列“memm”。
步驟4：將第一行的所有列設定為0。
步驟5：將第一列的所有行設定為0。
步驟6：使用for迴圈LOOP (idx_1 = 1 到 length1)
步驟7：使用內迴圈LOOP(idx_2 = 1 到 length2)
步驟8：檢查條件IF (string1[idx_1-1] == string2[idx_2-1] AND string1[idx_1-1] == 母音), THEN
步驟9：memm[idx_1][idx_2] = 1 + memm[idx_1-1][idx_2-1];
步驟10：否則 memm[idx_1][idx_2]=MAX(memm[idx_1][idx_2-1],memm[idx_1-1][idx_2])
步驟11：RETURN memm[length1][length2]
示例
#include <iostream>
using namespace std;
/**
* @param ch: character parameter
*
* @return true: if ch == vowel
* @return false: if ch == consonent
*/
bool checkVowel(char chr) {
switch(chr) {
case 'A':
case 'E':
case 'I':
case 'O':
case 'U':
case 'a':
case 'e':
case 'i':
case 'o':
case 'u':
return true;
break;
default:
return false;
break;
}
}
/**
* @param num1: first number
* @param num2: second number
*
* @return maximum number
*/
int maxx(int first, int second) {
if (first >= second)
return first;
else
return second;
}
/**
* @param string1: First String
* @param string2: Second String
*
* @return Length of maximum common subsequence containing vowels
*/
int LCSVowels(string string1, string string2) {
int length1 = string1.length();
int length2 = string2.length();
// create memory array for using Dynamic Programming
int memm[length1+1][length2+2];
// make first column zero
for (int idx_ = 0; idx_ <= length1; ++idx_) {
memm[idx_][0] = 0;
}
// make first row zero
for (int idx_=0; idx_ <= length2; ++idx_) {
memm[0][idx_] = 0;
}
// traverse the DP matrix
for (int idx_1=1; idx_1<=length1; ++idx_1) {
for (int idx_2=1; idx_2<=length2; ++idx_2) {
// if characters are equal and also they are vowels
if (string1[idx_1-1] == string2[idx_2-1] && checkVowel(string1[idx_1-1])) {
memm[idx_1][idx_2] = 1 + memm[idx_1-1][idx_2-1];
} else {
memm[idx_1][idx_2] = maxx(memm[idx_1][idx_2-1], memm[idx_1-1][idx_2]);
}
}
}
return memm[length1][length2];
}
int main() {
string string1, string2;
// Ask string 1
cout << "Enter String 1: ";
cin >> string1;
// Ask String 2
cout << "Enter String 2: ";
cin >> string2;
// call the function
int lcs = LCSVowels(string1, string2);
// display the result
cout << "Length of Longest Common Subsequence containing vowels: " << lcs << endl;
return 0;
}
輸出
Enter String 1: point Enter String 2: tutorials Length of Longest Common Subsequence containing vowels: 2
程式時間複雜度 = O(length1 x length2)
程式空間複雜度 = O(length1 x length2)
方法2：遞迴演算法
這是一種基於遞迴演算法的動態規劃方法。
演算法：LCS_Vowels(string1, string2, idx1, idx2, memm)
步驟1：IF (idx1 == -1 OR idx2 == -1), THEN RETURN 0
步驟2：IF (memm[idx1][idx2] != -1), THEN RETURN memm[idx1][idx2]
步驟3：IF (string1[idx_1] == string2[idx_2] AND string1[idx_1] == 母音), THEN
步驟4：memm[idx1][idx2] = 1 + LCS_Vowels(string1, string2, idx1-1, idx2-1, memm)
步驟5：否則，設定memm[idx1][idx2]=MAX(LCS_Vowels(string1, string2, idx1-1, idx2, memm)
, LCS_Vowels(string1, string2, idx1, idx2-1, memm))
步驟7：END IF
步驟8：RETURN memm[idx1][idx2]
示例
#include <iostream>
using namespace std;
/**
* @param ch: character parameter
*
* @return true: if ch == vowel
* @return false: if ch == consonent
*/
bool check_Vowel(char _chr) {
switch(_chr) {
case 'A':
case 'E':
case 'I':
case 'O':
case 'U':
case 'a':
case 'e':
case 'i':
case 'o':
case 'u':
return true;
break;
default:
return false;
break;
}
}
/**
* @param num1: first number
* @param num2: second number
*
* @return maximum number
*/
int maxx(int first, int second) {
if (first >= second)
return first;
else
return second;
}
/**
* @param ABC: First String
* @param XYZ: Second String
* @param ABC_IDX: index for string-A
* @param XYZ_IDX: index for string-B
* @param memm: DP matrix
*/
int LCS_Vowels(string ABC, string XYZ, int ABC_IDX, int XYZ_IDX, int memm[1000][1000]) {
if (ABC_IDX == -1 || XYZ_IDX == -1)
return 0;
if (memm[ABC_IDX][XYZ_IDX] != -1)
return memm[ABC_IDX][XYZ_IDX];
if (ABC[ABC_IDX] == XYZ[XYZ_IDX] && check_Vowel(ABC[ABC_IDX])) {
memm[ABC_IDX][XYZ_IDX] = LCS_Vowels(ABC, XYZ, ABC_IDX-1, XYZ_IDX-1, memm) + 1;
} else {
memm[ABC_IDX][XYZ_IDX] = maxx(
LCS_Vowels(ABC, XYZ, ABC_IDX-1, XYZ_IDX, memm),
LCS_Vowels(ABC, XYZ, ABC_IDX, XYZ_IDX-1, memm)
);
}
return memm[ABC_IDX][XYZ_IDX];
}
int main() {
string ABC, XYZ;
// Ask string 1
cout << "Enter String 1: ";
cin >> ABC;
// Ask String 2
cout << "Enter String 2: ";
cin >> XYZ;
int LENGTH_1 = ABC.length();
int LENGTH_2 = XYZ.length();
int memm[1000][1000];
for (int p=0; p<1000; ++p) {
for (int q=0; q<1000; ++q) {
memm[p][q] = -1;
}
}
// call the function
int lcs = LCS_Vowels(ABC, XYZ, LENGTH_1-1, LENGTH_2-1, memm);
// display the result
cout << "Length of Longest Common Subsequence containing vowels: " << lcs << endl;
return 0;
}
輸出
Enter String 1: longestsub Enter String 2: ohbekhfuo Length of Longest Common Subsequence containing vowels: 3
程式時間複雜度 = O(length1 x length2)
程式空間複雜度 = O(length1 x length2)
最後，本文描述了一個C++程式碼，它成功地利用動態規劃解決了給定的問題。這些演算法使用O(length1 x length2)的時間複雜度和空間複雜度來解決問題。
222 次瀏覽
