8000 New Problem Solution - "1849. Splitting a String Into Descending Cons… · royeLin/leetcode_cpp@83fa31a · GitHub
[go: up one dir, main page]
Skip to content

Commit 83fa31a

Browse files
haoelhaoel
committed
New Problem Solution - "1849. Splitting a String Into Descending Consecutive Values"
1 parent bf4fe68 commit 83fa31a

File tree

2 files changed

+101
-0
lines changed

2 files changed

+101
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,7 @@ LeetCode
99

1010
| # | Title | Solution | Difficulty |
1111
|---| ----- | -------- | ---------- |
12+
|1849|[Splitting a String Into Descending Consecutive Values](https://leetcode.com/problems/splitting-a-string-into-descending-consecutive-values/) | [C++](./algorithms/cpp/splittingAStringIntoDescendingConsecutiveValues/SplittingAStringIntoDescendingConsecutiveValues.cpp)|Medium|
1213
|1848|[Minimum Distance to the Target Element](https://leetcode.com/problems/minimum-distance-to-the-target-element/) | [C++](./algorithms/cpp/minimumDistanceToTheTargetElement/MinimumDistanceToTheTargetElement.cpp)|Easy|
1314
|1847|[Closest Room](https://leetcode.com/problems/closest-room/) | [C++](./algorithms/cpp/closestRoom/ClosestRoom.cpp)|Hard|
1415
|1846|[Maximum Element After Decreasing and Rearranging](https://leetcode.com/problems/maximum-element-after-decreasing-and-rearranging/) | [C++](./algorithms/cpp/maximumElementAfterDecreasingAndRearranging/MaximumElementAfterDecreasingAndRearranging.cpp)|Medium|

‎algorithms/cpp/splittingAStringIntoDescendingConsecutiveValues/SplittingAStringIntoDescendingConsecutiveValues.cpp

Lines changed: 100 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,100 @@
1+
// Source : https://leetcode.com/problems/splitting-a-string-into-descending-consecutive-values/
2+
// Author : Hao Chen
3+
// Date : 2021-05-03
4+
5+
/*****************************************************************************************************
6+
*
7+
* You are given a string s that consists of only digits.
8+
*
9+
* Check if we can split s into two or more non-empty substrings such that the numerical values of the
10+
* substrings are in descending order and the difference between numerical values of every two
11+
* adjacent substrings is equal to 1.
12+
*
13+
* For example, the string s = "0090089" can be split into ["0090", "089"] with numerical
14+
* values [90,89]. The values are in descending order and adjacent values differ by 1, so this way is
15+
* valid.
16+
* Another example, the string s = "001" can be split into ["0", "01"], ["00", "1"], or ["0",
17+
* "0", "1"]. However all the ways are invalid because they have numerical values [0,1], [0,1], and
18+
* [0,0,1] respectively, all of which are not in descending order.
19+
*
20+
* Return true if it is possible to split s​​​​​​ as described above, or false otherwise.
21+
*
22+
* A substring is a contiguous sequence of characters in a string.
23+
*
24+
* Example 1:
25+
*
26+
* Input: s = "1234"
27+
* Output: false
28+
* Explanation: There is no valid way to split s.
29+
*
30+
* Example 2:
31+
*
32+
* Input: s = "050043"
33+
* Output: true
34+
* Explanation: s can be split into ["05", "004", "3"] with numerical values [5,4,3].
35+
* The values are in descending order with adjacent values differing by 1.
36+
*
37+
* Example 3:
38+
*
39+
* Input: s = "9080701"
40+
* Output: false
41+
* Explanation: There is no valid way to split s.
42+
*
43+
* Example 4:
44+
*
45+
* Input: s = "10009998"
46+
* Output: true
47+
* Explanation: s can be split into ["100", "099", "98"] with numerical values [100,99,98].
48+
* The values are in descending order with adjacent values differing by 1.
49+
*
50+
* Constraints:
51+
*
52+
* 1 <= s.length <= 20
53+
* s only consists of digits.
54+
******************************************************************************************************/
55+
56+
class Solution {
57+
private:
58+
int pos;
59+
public:
60+
bool getNum(string& s, long target) {
61+
62+
long n = 0;
63+
while(s[pos] == '0') pos++;
64+
while(pos < s.size()){
65+
n = (n*10 + s[pos++] - '0') ;
66+
if (n == target) return true;
67+
if (n > target ) return false; // n is already greater than target
68+
}
69+
return target == n;
70+
}
71+
72+
long firstNum(string& s, int len) {
73+
long n = 0;
74+
while(s[pos] == '0') pos++;
75+
for(; pos< s.size() && len > 0; pos++, len--) {
76+
n = (n*10 + s[pos] - '0') ;
77+
}
78+
return n;
79+
}
80+
81+
bool splitString(string s) {
82+
pos = 0;
83+
long num;
84+
for (int len=1; len<= s.size()/2+1; len++) {
85+
pos = 0;
86+
num = firstNum(s, len);
87+
if (pos >= s.size()) continue; // only have one number
88+
89+
bool result = true;
90+
while( pos < s.size() ) {
91+
if (getNum(s, --num) == false){
92+
result = false;
93+
break;
94+
}
95+
}
96+
if (result) return true;
97+
}
98+
return false;
99+
}
100+
};

0 commit comments

Comments
 (0)
0