392. Is Subsequence
Medium
Given a string s and a string t, check if s is subsequence of t.
You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).
Example 1:
s = "abc", t = "ahbgdc"
Return true.
題目大意：給兩個字符串s和t，判斷s是不是t的子串。s是t的子串意味著可以通過刪除一些字符t中的字符得到s独撇。
解題方法：維護兩個指針亮蒋，分別指向s和t谎碍，遇到相同的字符則推進指針，若s中所有的字符都可以在t中找到，s是t的子串。
class Solution(object):
def isSubsequence(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
i, j = 0, 0
while i < len(s) and j < len(t):
if s[i] == t[j]:
i += 1
j += 1
return i == len(s) #True if all characters in s have been found in t
測試一下
Success
[Details]
Runtime: 240 ms, faster than 20.36% of Python online submissions for Is Subsequence.
Memory Usage: 19 MB, less than 63.56% of Python online submissions for Is Subsequence.
394. Decode String
Medium
Given an encoded string, return it's decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.
You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.
Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].
Examples:
s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
題目大意：給一個字符串的縮寫种呐，解析它得到全稱。
解題思路：順序解析縮寫字符串弃甥，從'['開始爽室，到']'結(jié)束。
class Solution(object):
def decodeString(self, s):
"""
:type s: str
:rtype: str
"""
idx = 0
(ans, idx) = self.decodeStringHelper(s, idx)
return ans
def decodeStringHelper(self, s, idx):
ans = ''
# continue searching if reach end of string or ']'
while idx < len(s) and s[idx] != ']':
if s[idx].isdigit():
repeats = 0
# occur repeats num
while idx < len(s) and s[idx].isdigit():
repeats = repeats*10 + int(s[idx])
idx += 1
idx += 1 # skip '['
# handle the string that needs to repeats
(temp, idx) = self.decodeStringHelper(s, idx)
idx += 1 # skip ']'
ans += temp*repeats
else:
ans += s[idx]
idx += 1
return (ans, idx)
測試一下
Success
[Details]
Runtime: 16 ms, faster than 93.20% of Python online submissions for Decode String.
Memory Usage: 11.9 MB, less than 9.04% of Python online submissions for Decode String.
