{"id":4927,"date":"2019-03-02T20:33:10","date_gmt":"2019-03-03T04:33:10","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4927"},"modified":"2019-03-02T20:33:34","modified_gmt":"2019-03-03T04:33:34","slug":"leetcode-1003-check-if-word-is-valid-after-substitutions","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/uncategorized\/leetcode-1003-check-if-word-is-valid-after-substitutions\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1003. Check If Word Is Valid After Substitutions"},"content":{"rendered":"\n

We are given that the string \"abc\"<\/code> is valid.<\/p>\n\n\n\n

From any valid string V<\/code>, we may split V<\/code> into two pieces X<\/code> and Y<\/code> such that X + Y<\/code> (X<\/code> concatenated with Y<\/code>) is equal to V<\/code>.  (X<\/code> or Y<\/code> may be empty.)  Then, X + \"abc\" + Y<\/code> is also valid.<\/p>\n\n\n\n

If for example S = \"abc\"<\/code>, then examples of valid strings are: \"abc\", \"aabcbc\", \"abcabc\", \"abcabcababcc\"<\/code>.  Examples of invalid<\/strong> strings are: \"abccba\"<\/code>, \"ab\"<\/code>, \"cababc\"<\/code>, \"bac\"<\/code>.<\/p>\n\n\n\n

Return true<\/code> if and only if the given string S<\/code> is valid.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input: <\/strong>\"aabcbc\"\nOutput: <\/strong>true\nExplanation: <\/strong>\nWe start with the valid string \"abc\".\nThen we can insert another \"abc\" between \"a\" and \"bc\", resulting in \"a\" + \"abc\" + \"bc\" which is \"aabcbc\".\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input: <\/strong>\"abcabcababcc\"\nOutput: <\/strong>true\nExplanation: <\/strong>\n\"abcabcabc\" is valid after consecutive insertings of \"abc\".\nThen we can insert \"abc\" before the last letter, resulting in \"abcabcab\" + \"abc\" + \"c\" which is \"abcabcababcc\".\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input: <\/strong>\"abccba\"\nOutput: <\/strong>false\n<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
Input: <\/strong>\"cababc\"\nOutput: <\/strong>false<\/pre>\n\n\n\n
Note:<\/strong><\/p>\n\n\n\n
  1. 1 <= S.length <= 20000<\/code><\/li>
  2. S[i]<\/code> is 'a'<\/code>, 'b'<\/code>, or 'c'<\/code><\/li><\/ol>\n\n\n\n
    Solution: Stack<\/strong><\/h2>\n\n\n\n
    If current char can be appended to the stack do so, if the top of stack is “abc” pop, otherwise push the current char to the stack. Check whether the stack is empty after all chars were processed.<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua, running time: 28 ms, 11.9 MB\nclass Solution {\npublic:\n  bool isValid(string S) {\n    stack st;\n    for (char ch : S) {\n      if (st.empty()) {\n        st.push(\"\");\n      }\n      string& s = st.top();\n      char exp = 'a' + s.length();\n      if (ch == exp) {\n        s += ch;\n        if (s == \"abc\") st.pop();\n      } else if (ch != 'a'){\n        return false;        \n      } else {\n        st.push(\"a\");\n      }\n    }\n    return st.empty();\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-4927","post","type-post","status-publish","format-standard","hentry","category-uncategorized","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4927","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4927"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4927\/revisions"}],"predecessor-version":[{"id":4929,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4927\/revisions\/4929"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4927"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4927"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4927"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}