-
Notifications
You must be signed in to change notification settings - Fork 0
/
1003.check-if-word-is-valid-after-substitutions.java
119 lines (109 loc) · 2.26 KB
/
1003.check-if-word-is-valid-after-substitutions.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
/*
* @lc app=leetcode id=1003 lang=java
*
* [1003] Check If Word Is Valid After Substitutions
*
* https://leetcode.com/problems/check-if-word-is-valid-after-substitutions/description/
*
* algorithms
* Medium (54.19%)
* Likes: 156
* Dislikes: 254
* Total Accepted: 18.5K
* Total Submissions: 34.1K
* Testcase Example: '"aabcbc"'
*
* We are given that the string "abc" is valid.
*
* From any valid string V, we may split V into two pieces X and Y such that X
* + Y (X concatenated with Y) is equal to V. (X or Y may be empty.) Then, X
* + "abc" + Y is also valid.
*
* If for example S = "abc", then examples of valid strings are: "abc",
* "aabcbc", "abcabc", "abcabcababcc". Examples of invalid strings are:
* "abccba", "ab", "cababc", "bac".
*
* Return true if and only if the given string S is valid.
*
*
*
* Example 1:
*
*
* Input: "aabcbc"
* Output: true
* Explanation:
* We start with the valid string "abc".
* Then we can insert another "abc" between "a" and "bc", resulting in "a" +
* "abc" + "bc" which is "aabcbc".
*
*
*
* Example 2:
*
*
* Input: "abcabcababcc"
* Output: true
* Explanation:
* "abcabcabc" is valid after consecutive insertings of "abc".
* Then we can insert "abc" before the last letter, resulting in "abcabcab" +
* "abc" + "c" which is "abcabcababcc".
*
*
*
* Example 3:
*
*
* Input: "abccba"
* Output: false
*
*
*
* Example 4:
*
*
* Input: "cababc"
* Output: false
*
*
*
*
*
*
* Note:
*
*
* 1 <= S.length <= 20000
* S[i] is 'a', 'b', or 'c'
*
*
*
*
*
*
*
*
*
*/
// @lc code=start
// 1003. Check If Word Is Valid After Substitutions
// stack + greedy : when find a "abc" remove it.
class Solution {
public boolean isValid(String S) {
if (S.length() == 0) return false;
Stack<Character> s = new Stack<>();
for (char c : S.toCharArray()) {
if (c == 'c') {
if (s.size() < 2) return false;
if (s.peek() != 'b') return false;
s.pop();
if (s.peek() != 'a') return false;
s.pop();
} else {
s.push(c);
}
}
return s.isEmpty();
}
}
// @lc code=end