本文共 1772 字，大约阅读时间需要 5 分钟。

LeetCode刷题：1003. Check If Word Is Valid After Substitutions

原题链接：

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'

---

算法设计

class Solution {    public boolean isValid(String S) {        Stack
   
     stack = new Stack<>();        for(char ch : S.toCharArray()){            switch(ch){                case 'a':                case 'b': stack.push(ch); break;                case 'c':                    if(!stack.isEmpty() && stack.peek() == 'b')                        stack.pop();                    else                        return false;                    if(!stack.isEmpty() && stack.peek() == 'a')                        stack.pop();                    else                        return false;                    break;            }        }        return stack.isEmpty();         }}
   

程序运行结果，Accepted.

 

转载地址：http://pntdi.baihongyu.com/