文章目錄
-
- 1. 題目
- 2. 解題
1. 題目
給你一個僅由數字組成的字元串 s 。
請你判斷能否将 s 拆分成兩個或者多個 非空子 字元串 ，使子字元串的 數值 按 降序 排列，且每兩個 相鄰子字元串 的數值之 差 等于 1 。
例如，字元串
s = "0090089"
可以拆分成
["0090", "089"]
，數值為
[90,89]
。這些數值滿足按降序排列，且相鄰值相差 1 ，這種拆分方法可行。
另一個例子中，字元串
s = "001"
可以拆分成
["0", "01"]、["00", "1"]
或
["0", "0", "1"]
。然而，所有這些拆分方法都不可行，因為對應數值分别是 [0,1]、[0,1] 和 [0,0,1] ，都不滿足按降序排列的要求。
如果可以按要求拆分 s ，傳回 true ；否則，傳回 false 。
子字元串 是字元串中的一個連續字元序列。
示例 1：
輸入：s = "1234"
輸出：false
解釋：不存在拆分 s 的可行方法。
示例 2：
輸入：s = "050043"
輸出：true
解釋：s 可以拆分為 ["05", "004", "3"] ，對應數值為 [5,4,3] 。
滿足按降序排列，且相鄰值相差 1 。
示例 3：
輸入：s = "9080701"
輸出：false
解釋：不存在拆分 s 的可行方法。
示例 4：
輸入：s = "10009998"
輸出：true
解釋：s 可以拆分為 ["100", "099", "98"] ，對應數值為 [100,99,98] 。
滿足按降序排列，且相鄰值相差 1 。
提示：
1 <= s.length <= 20
s 僅由數字組成 複制
來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/splitting-a-string-into-descending-consecutive-values
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
2. 解題
class Solution {
bool can = false;
public:
bool splitString(string s) {
dfs(s, LONG_LONG_MAX, 0);
return can;
}
void dfs(string s, long long prevVal, int ct)
{
if(can) return; // 找到解了
if(s == ""){
if(ct > 1) // 個數至少為 2
can = true;
return;
}
long long curVal = 0;
for(int i = 0; i < s.size(); i++)
{
if(curVal >= LONG_LONG_MAX/10)
break; // 目前數字超過範圍，肯定不存在解
// LLMAX : 9223372036854775807, 19位
curVal = curVal*10 + s[i]-'0';
if(prevVal - curVal < 1)
break; // curval 越來越大，不存在降序的
else if(prevVal == LONG_LONG_MAX || prevVal - curVal == 1)
{
dfs(s.substr(i+1), curVal, ct+1);
}
}
}
}; 複制
0 ms 5.9 MB C++
我的CSDN部落格位址 https://michael.blog.csdn.net/
長按或掃碼關注我的公衆号（Michael阿明），一起加油、一起學習進步！