資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中的廣義縮寫
假設有一個單詞。我們需要定義一個函式，該函式可以生成該單詞的廣義縮寫。
因此，如果輸入像“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 := 從索引 0 到 idx - 1 的 s 的子字串
i := y 的大小
num := 空字串
當 (i >= 0 且 y[i] <= '9' 的 ASCII 碼 且 y[i] >= '0' 的 ASCII 碼) 時，執行：
num := y[i] + num
(將 i 減 1)
如果 i 不等於 y 的大小，則：
ret := 從索引 (0 到 idx - (y 的大小 - 1 - i) - 1) 的 s 的子字串連線 (number + 1) 作為字串連線從索引 (0 到 idx) 的 s 的子字串
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, ]
更新於： 2020-11-18
203 次檢視
廣告