สมมติว่ามีคำ เราต้องกำหนดฟังก์ชันที่สามารถสร้าง generalized abbreviations ของคำนั้นได้
เช่น ถ้าอินพุทเป็น "word" ผลลัพธ์จะเป็น ["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้ −
กำหนดอาร์เรย์ ret
กำหนดฟังก์ชัน solve() รับ s, idx
ถ้า idx >= ขนาดของ s แล้ว −
แทรก s ที่ท้ายของ ret
คืนค่า
y := substring ของ s จากดัชนี 0 ถึง idx - 1
i := ขนาดของ y
num := สตริงว่าง
ลูป while (i >= 0 และ y[i] <= ASCII ของ '9' และ y[i] >= ASCII ของ '0') ทำ −
num := y[i] + num
ลด i ลง 1
ถ้า i ไม่เท่ากับขนาดของ y แล้ว −
ret := substring ของ s จากดัชนี (0 ถึง idx - (ขนาดของ y - 1 - i) - 1) ต่อ (number + 1) เป็นสตริง ต่อ substring ของ s จากดัชนี (0 ถึง idx)
s1 := num + 1 เป็นสตริง
s2 := num เป็นสตริง
ถ้าขนาดของ s1 เท่ากับขนาดของ s2 แล้ว −
มิฉะนั้น
solve(ret, idx + 1)
มิฉะนั้น
prev := s[idx]
s[idx] := '1'
solve(s, idx + 1)
s[idx] := prev
solve(s, idx + 1)
จากเมธอดหลักทำดังนี้ −
solve(word, 0)
คืนค่า ret
ตัวอย่าง
ลองดูการติดตั้งต่อไปนี้เพื่อให้เข้าใจได้ดีขึ้น −
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } class Solution { public: vector<string> ret; void solve(string s, int idx){ if (idx >= s.size()) { ret.push_back(s); return; } string y = s.substr(0, idx); int i = y.size() - 1; string num = ""; while (i >= 0 && y[i] <= '9' && y[i] >= '0') { num = y[i] + num; i--; } if (i != y.size() - 1) { string ret = s.substr(0, idx - (y.size() - 1 - i)) + to_string(stoi(num) + 1) + s.substr(idx + 1); string s1 = to_string(stoi(num) + 1); string s2 = to_string(stoi(num)); if (s1.size() == s2.size()) solve(ret, idx); else solve(ret, idx + 1); } else { char prev = s[idx]; s[idx] = '1'; solve(s, idx + 1); s[idx] = prev; } solve(s, idx + 1); } vector<string> generateAbbreviations(string word){ solve(word, 0); return ret; } }; main(){ Solution ob; print_vector(ob.generateAbbreviations("hello")); } อินพุท
hello
เอาต์พุท
[5, 4o, 3l1, 3lo, 2l2, 2l1o, 2ll1, 2llo, 1e3, 1e2o, 1e1l1, 1e1lo, 1el2, 1el1o, 1ell1, 1ello, h4, h3o, h2l1, h2lo, h1l2, h1l1o, h1ll1, h1llo, he3, he2o, he1l1, he1lo, hel2, hel1o, hell1, hello, ]
