นี่คือปัญหาเชิงสนุกสนานเกี่ยวกับการย่อตัวอักษรตัวเลขของสตริงที่กำหนด ความยาวสตริงน้อยกว่า 10 จะพิมพ์การย่อทั้งหมด
การย่อตัวอักษรตัวเลขเป็นรูปแบบตัวอักษรผสมกับตัวเลข ค่าของตัวเลขคือจำนวนตัวอักษรที่ข้ามไป อาจมีสับสตริงที่ข้ามได้หลายอัน ไม่มีสองสับสตริงติดกัน
อัลกอริทึม
printAbbreviation(s, index, max, str) -
begin
if index is same as max, then
print str
end if
add s[index] at the last of str
printAbbreviation(s, index + 1, max, str)
delete last character from str
count := 1
if str is not empty, then
if the last character of str is a digit, then
add last digit with the count value
delete last character from str
end if
end if
add count after the str
printAbbreveation(s, index + 1, max, str)
end
ตัวอย่างโค้ด C++
#includeusing namespace std; void printAbbreviation(const string& s, int index, int max_index, string str) { if (index == max_index) { // ถ้าสตริงจบ cout << str << endl; return; } str.push_back(s[index]); // เพิ่มตัวอักษรปัจจุบันเข้าผลลัพธ์ printAbbreviation(s, index + 1, max_index, str); // พิมพ์จากดัชนีถัดไป str.pop_back(); // ลบตัวอักษรสุดท้าย int count = 1; if (!str.empty()) { if (isdigit(str.back())) { // ถ้าตัวสุดท้ายเป็นตัวเลข count += (int)(str.back() - '0'); // นับค่าตัวเลขนั้น str.pop_back(); // ลบตัวอักษรสุดท้าย } } char to_char = (char)(count + '0'); // แปลง count เป็นตัวอักษร str.push_back(to_char); printAbbreviation(s, index + 1, max_index, str); // ทำต่อไปดัชนีถัดไป } void printCombination(string str) { if (!str.length()) // ถ้าสตริงว่าง return; string str_res; printAbbreviation(str, 0, str.length(), str_res); } int main() { string str = "HELLO"; printCombination(str); }
ผลลัพธ์
HELLO HELL1 HEL1O HEL2 HE1LO HE1L1 HE2O HE3 H1LLO H1LL1 H1L1O H1L2 H2LO H2L1 H3O H4 1ELLO 1ELL1 1EL1O 1EL2 1E1LO 1E1L1 1E2O 1E3 2LLO 2LL1 2L1O 2L2 3LO 3L1 4O 5
