leetcode 8.24-8.30

2020-08-25

459 重复的字符串
337 打家劫舍III

459. 重复的字符串

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

示例 1:

输入: “abcabcabcabc”

输出: True

解释: 可由子字符串 “abc” 重复四次构成。 (或者子字符串 “abcabc” 重复两次构成。)

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/repeated-substring-pattern
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的解法：由一个子串重复多次构成=>$s = s’ * n$，n的取值范围是[2, len(s)]

双字符串法：看题解，将两个 ss 连在一起，并移除第一个和最后一个字符。如果 ss 是该字符串的子串，那么 ss就满足题目要求。正确性需要证明。

class Solution(object):
    def repeatedSubstringPattern(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if len(s) < 2:
            return False
        for times in range(2, len(s)+1):
            if len(s) % times != 0:
                continue
            if s == s[:(len(s) / times)] * times:
                return True
        return False
      	
        # 双字符串
        return (s + s).find(s, 1) != len(s)

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入：”23”
输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：递归，长度为n的数字字符串字母组合为第n个数字对应的字母与前n-1个数字对应的字母组合的组合

官方题解是回溯

AC代码：

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        telephone = {'2':"abc", '3':"def", '4':"ghi", '5':"jkl", '6':"mno", '7':"pqrs", '8':"tuv", '9':"wxyz"}
        if len(digits) == 0:
            return []
        if len(digits) == 1:
            return list(telephone[digits[0]])
        
        tmp_ret = self.letterCombinations(digits[:-1])
        ret = []
        for ch in telephone[digits[-1]]:
            for s in tmp_ret:
                ret.append(s + ch)
        
        return ret