狗家conversion两轮

1. def findAllIndex2(s, t):
   
2.     map = {}
   
3.     for i, c in enumerate(s):
   
4.         if c not in map:
   
5.             map[c] = []
   
6.             map[c] += i,
   
7.         else:
   
8.             map[c] += i,
   
9. 
   
10.     res = []
    
11. 
    
12.     def backtracking(res, map, t, start, tmp):
    
13.         if start >= len(t):
    
14.             new = []
    
15.             for t in tmp:
    
16.                 new.append(t)
    
17.             res += new,
    
18.             return
    
19.         indexes = map[t[start]] if t[start] in map else []
    
20. 
    
21.         for i in range(len(indexes)):
    
22.             tmp += indexes[i],
    
23.             backtracking(res, map, t, start + 1, tmp)
    
24.             tmp.pop()
    
25. 
    
26.     backtracking(res, map, t, 0, [])
    
27.     return res
    
28. 
    
29. 
    
30. print(findAllIndex2('abccddee', 'ade'))

复制代码

第一题是不是这样：target是adee和aede返回的解答的个数都是相同的，所以只需要把相同char group在一起，比如adee，然后对每个char找到可能的index，然后直接就是所有index的combination，比如原字符如果4个e，那么任意选出2个就是一个组合，不明白楼主的dfs什么意思，需要考虑什么顺序吗？

能不能拿return offer其实主要是看你项目做得如何，你的host给你写的评语怎么样。面试只要不太差不会成为不给offer的原因。

wtcupup 发表于 2017-10-1 15:18

21行到24行貌似不对吧，你从indexes里面取出一个index，是不是就不能再用作相同的char了？比如taget是adee，如果第一个e用了某个index，第二个e应该不能再用了。

returning 发表于 2017-10-2 14:42
21行到24行貌似不对吧，你从indexes里面取出一个index，是不是就不能再用作相同的char了？比如taget是ade ...

多谢指正

1. def findAllIndex2(s, t):
   
2.     map = {}
   
3.     for i, c in enumerate(s):
   
4.         if c not in map:
   
5.             map[c] = []
   
6.             map[c] += i,
   
7.         else:
   
8.             map[c] += i,
   
9. 
   
10.     res = []
    
11.     visited = set()
    
12. 
    
13.     def backtracking(res, map, t, start, tmp, visited):
    
14.         if start >= len(t):
    
15.             res += list(tmp),
    
16.             return
    
17.         indexes = map[t[start]] if t[start] in map else []
    
18. 
    
19.         for i in indexes:
    
20.             if i not in visited:
    
21.                 tmp += i,
    
22.                 visited.add(i),
    
23.                 backtracking(res, map, t, start + 1, tmp, visited)
    
24.                 tmp.pop()
    
25.                 visited.remove(i)
    
26. 
    
27. 
    
28.     backtracking(res, map, t, 0, [], visited)
    
29.     s = [sorted(i) for i in res]
    
30.     return [s[i] for i in range(len(s)) if i == 0 or s[i] != s[i-1]]
    
31. 
    
32. 
    
33. print(findAllIndex2('abccddee', 'adee'))

复制代码

求教楼主：记忆化+搜索 不是 DP吗？

david.fang 发表于 2017-10-2 15:24
求教楼主：记忆化+搜索 不是 DP吗？

就是DP啊

wtcupup 发表于 2017-10-2 15:18
多谢指正

感觉可以递归函数里加一个pos记录之前访问到了s的哪一位，这样就不需要visited，也不需要在最后去重了