题290（easy）
题目要求如果pattern里的字母重复模式和单词重复模式一致，就返回true,否则返回false。
Given a pattern and a string str, find if str follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.
Examples:
1.pattern = “abba”, str = “dog cat cat dog” should return true.
2.pattern = “abba”, str = “dog cat cat fish” should return false.
3.pattern = “aaaa”, str = “dog cat cat dog” should return false.
4.pattern = “abba”, str = “dog dog dog dog” should return false.
思路是首先将str中的单词分离出来。然后用一个list1保存所有pattern的不同状态，比如’a’’b’’c’。用另一个list2保存pattern 和str单词的对应关系。如果list2的数量大于list1的数量，则代表有不同的对应关系出现，即出现了和模式不一样的对应，则返回False。
代码如下：
class Solution(object):
def wordPattern(self, pattern, str):
"""
:type pattern: str
:type str: str
:rtype: bool
"""
num=[]
for i in range(len(pattern)): #分出str中的单词
num.append(str.split(' ')[i])
res=[]
biao1=[] # 存储[pattern word]对
biao2=set(pattern) # 存储不同的pattern
for i in range(len(pattern)):
res.append([pattern[i],num[i]])
for j in res:
if j not in biao1:
biao1.append(j)
if len(biao1)>len(biao2): # 如果有大于pattern数目的对应关系代表，代表了出现和pattern不一样的关系
return False
else:
return True
pa="abba"
num="cat dog cat cat"
s=Solution()
print(s.wordPattern(pa,num))
结果：
题17 （medium）
题目要求是输出对应电话机数字的字母小标，如下图所示。
示例：
Input:Digit string “23”
Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
我的思路是:
1.首先挑出输入数字所对应的字母存入res[],对应长度就是我们要选出的字母的长度l
2.首先tmp赋值res[0],对应第一个字母的所有选择。（注意这里我用了copy.copy()只进行值的复制，否则之后res数组会变化）
3.进行剩下的l-1次选择，利用遍历把当前res中的数添加到之前tmp中的数的末尾，然后进行长度判断:
长度=i+1对应于上次选择的结束，该次直接在后面添加这次的选择即可。如果长度已经达到指定要求，将结果append到res1。
最后返回res1即可。
代码如下：
import copy
class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
if digits=="":
return []
res = [] # 存储挑出来的数字对应的字母
res1 = [] # 存储结果
nums = [[],['a','b','c'],['d','e','f'],['g','h','i'],
['j','k','l'],['m','n','o'],['p','q','r','s'],
['t','u','v'],['w','x','y','z'], ['+'],
[''],['#']]
l = len(digits)
for i in range(l):
di = int(digits[i])-
res.append(nums[di])
tmp = copy.copy(res[])
if l==:
return tmp
for i in range(l-): # 挑选次数
for j in res[i+]:
for n in j:
for k in tmp:
if len(k)==i+:
tmp.append(k+n)
if len(k+n)==l:
res1.append(k+n) # 如果达到指定长度就结束，增加结果到res1
continue
return res1
s = Solution()
print(s.letterCombinations("23"))
结果如下：
题605（easy）
题目是说玩一个养花游戏，有1的位置代表有花种在这里，花只能种在list中为0的位置，且该位置左右不能为1。
Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.
Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.
Example 1:
Input: flowerbed = [1,0,0,0,1], n = 1
Output: True
Example 2:
Input: flowerbed = [1,0,0,0,1], n = 2
Output: False
我的思路如下：
1.种花时不仅考虑该位置为空，同时它的左右两边都要为空。
2.当种下花后，把该位置左右两边的值都设为1,表示下一次种花不能种在这里。
3.如果能成功种植的花把位置传给res相应位置，不能种植的花，值设为-1
4.最后判断res中是否有-1的存在，若有，则不能成功种花，返回False。
代码如下：
class Solution:
def canPlaceFlowers(self, flowerbed, n):
"""
:type flowerbed: List[int]
:type n: int
:rtype: bool
"""
res=[- for i in range(n)]
for i in range(n):
if flowerbed[]== and flowerbed[]==:
flowerbed[]=
flowerbed[]=
res[i]=
if flowerbed[-]== and flowerbed[-]==:
flowerbed[-]=
flowerbed[-]=
res[i]=len(flowerbed)-
for j in range(,len(flowerbed)-):
if flowerbed[j]== and flowerbed[j-]== \
and flowerbed[j+]==:
flowerbed[j]=
flowerbed[j-]=
flowerbed[j+]=
res[i]=j
if - in res:
return False
else:
return True
flowerbed=[,,,,]
s = Solution()
print(s.canPlaceFlowers(flowerbed,))
结果如下：