Pinterest 电面coding

#1 Same as  


#2 follow up:
Reverse look and sa

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

l of edge cases, there could be invalid output.

你return一个list怎么可能用dp做，明显应该是backtrack

不是已经hire freeze了吗 楼主什么时候面的？

这个follow up怎么用dp解决呀？

top down版：

1. import java.util.*;
   
2. 
   
3. public class CountAndSay2 {
   
4.     public static List<String> solution(String input) {
   
5.         Map<Integer, List<String>> memo = new HashMap<>();
   
6. 
   
7.         return helperWithMeomory(memo, input, 0);
   
8.     }
   
9. 
   
10. 
    
11. 
    
12.     private static List<String> helperWithMeomory(Map<Integer, List<String>> memo, String input, int start) {
    
13.         if (memo.containsKey(start)) {
    
14.             return memo.get(start);
    
15.         }
    
16. 
    
17.         if (start == input.length()) {
    
18.             return Arrays.asList("");
    
19.         }
    
20.         List<String> res = new LinkedList<>();
    
21.         if (input.charAt(start) == '0') {
    
22.             memo.put(start, res);
    
23.             return res;
    
24.         }
    
25. 
    
26. 
    
27.         for (int i = start; i < input.length() - 1; i++) {
    
28.             int count = Integer.parseInt(input.substring(start, i + 1));
    
29.             int num = input.charAt(i + 1) - '0';
    
30.             StringBuilder sb = new StringBuilder();
    
31.             for (int j = 0; j < count; j++) {
    
32.                 sb.append(num);
    
33.             }
    
34.             String strToAdd = sb.toString();
    
35.             List<String> tempList = helperWithMeomory(memo, input, i + 2);
    
36.             for (String tempStr : tempList) {
    
37.                 res.add(strToAdd + tempStr);
    
38.             }
    
39.         }
    
40. 
    
41.         memo.put(start, res);
    
42. 
    
43.         return res;
    
44.     }
    
45. 
    
46.     public static void main(String[] args) {
    
47.         System.out.println(solution("1112"));
    
48.     }
    
49. }

复制代码