ในปัญหานี้ เราได้รับสตริงและเราต้องหาสตริงย่อยจากสตริงที่กำหนด สตริงย่อยที่จะพบควรเริ่มต้นด้วย สระ และลงท้ายด้วยอักขระคงที่
สตริง เป็นอาร์เรย์ของอักขระ
สตริงย่อยที่จะถูกสร้างขึ้นในปัญหานี้ สามารถสร้างได้โดยการลบอักขระบางตัวของสตริง และโดยไม่เปลี่ยนลำดับของสตริง
Input: ‘abc’ Output: ab, ac, abc
เพื่อแก้ปัญหานี้ เราจะวนซ้ำสตริงและแก้ไขเสียงสระ และตรวจสอบลำดับถัดไป มาดูอัลกอริธึมเพื่อค้นหาวิธีแก้ปัญหากัน −
อัลกอริทึม
Step 1: Iterate of each character of the string, with variable i. Step 2: If the ith character is a vowel. Step 3: If the jth character is a consonant. Step 4: Add to the HashSet, substring from 1st character to jth character. Step 5: Repeat the following steps and find substrings from the string.
ในการวนซ้ำ เราจะวนซ้ำทุกสตริง ตั้งแต่ 1 ถึง 2 legth(string) -1.
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
string subString(string s, int binary){
string sub = "";
int pos;
while(binary>0){
pos=log2(binary&-binary)+1;
sub=s[pos-1]+sub;
binary= (binary & ~(1 << (pos-1)));
}
reverse(sub.begin(),sub.end());
return sub;
}
void findAllSubStrings(string s){
map<int, set<string> > sorted_subsequence;
int len = s.size();
int limit = pow(2, len);
for (int i = 1; i <= limit - 1; i++) {
string sub = subString(s, i);
sorted_subsequence[sub.length()].insert(sub);
}
for (auto it : sorted_subsequence) {
for (auto ii : it.second)
cout<<ii<<" ";
cout<<"\t";
}
}
int main() {
string s = "wxyz";
cout<<"The substring are :\n";
findAllSubStrings(s);
return 0;
} ผลลัพธ์
สตริงย่อยคือ −
w x y z wx wy wz xy xz yz wxy wxz wyz xyz wxyz
