贴段实现题求更高效解法

leetcode 17变种
原题是一个字符，map 一个数组中任意一个字符
变种是：多个字符，map一个string
        map.put("1","abc");
        map.put("2","bcd");
        map.put("3","def");
        map.put("4","gg");
        map.put("12","yy");
        map.put("23","dx");
        map.put("34","gwew");
        map.put("234","wsgvw");

给“1234”，输入各种可能的组合
我个code: 直接套用word breakII
拿到组合的list后
遍历每个组合，再map到value,  感觉这个太土了，有没有更好的解法
code 先贴上

1. import java.util.ArrayList;
   
2. import java.util.Arrays;
   
3. import java.util.HashMap;
   
4. import java.util.List;
   
5. 
   
6. public class LetterCombinationsofaPhoneNumber_2 {
   
7.     public List<String> letterCombinations_valuesAreString(String s) {
   
8.         HashMap<String,String > map = new HashMap<String, String>();
   
9.         map.put("1","abc");
   
10.         map.put("2","bcd");
    
11.         map.put("3","def");
    
12.         map.put("4","gg");
    
13.         map.put("12","yy");
    
14.         map.put("23","dx");
    
15.         map.put("34","gwew");
    
16.         map.put("234","wsgvw");
    
17.         List<String> keys=new ArrayList<>();
    
18.         for(String key: map.keySet())
    
19.             keys.add(key);
    
20.         List<String> combinationList = new ArrayList<String>();
    
21.         combinationList=DFS(s, keys,new HashMap<String, List<String>> ());
    
22.         List<String> res=new ArrayList<>();
    
23. 
    
24.         for(String combination:combinationList){
    
25.             StringBuilder sb=new StringBuilder();
    
26.             String[] strs=combination.split(" ");
    
27.             for(String str:strs)
    
28.                 sb.append(map.get(str));
    
29.             res.add(sb.toString());
    
30.             System.out.println();
    
31.         }
    
32.         return res;
    
33.     }
    
34. 
    
35.     public List<String> DFS(String s, List<String> wordDict,
    
36.                             HashMap<String, List<String>> memory){
    
37.         if(s.length()==0)
    
38.             return Arrays.asList(new String[]{""});
    
39. 
    
40.         if(memory.containsKey(s))
    
41.             return memory.get(s);
    
42. 
    
43.         List<String> res = new ArrayList<>();
    
44. 
    
45.         for(String word : wordDict){
    
46.             if(s.startsWith(word)){
    
47.                 for(String postfix : DFS(s.substring(word.length()),
    
48.                         wordDict,memory)){
    
49.                     if(postfix.length()==0){
    
50.                         res.add(word);
    
51.                     }else{
    
52.                         res.add(word + " " + postfix);
    
53.                     }
    
54.                 }
    
55.             }
    
56.         }
    
57. 
    
58.         memory.put(s, res);
    
59.         return memory.get(s);
    
60.     }
    
61. 
    
62. 
    
63.     public static void main(String [] args){
    
64.         LetterCombinationsofaPhoneNumber_2 test=new LetterCombinationsofaPhoneNumber_2();
    
65.         List<String> res=test.letterCombinations_valuesAreString("1234");
    
66.         System.out.print(res);
    
67.     }

复制代码

看了你的解法时间复杂度应该是O(n^2)，个人认为这个不只是的上界，也是严格的下界Ω(n^2)，应该不可能有方法比这个更快了，至于原因我们可以分析一下额。

首先，我们假象另一种变种，你原变种map不是所有组合都有对应的映射关系，而我们假象的新变种所有的组合都有映射关系，比如"1234"，所有的映射关系即为：

1.         map.put( "1", "abc" );
   
2.         map.put( "2", "bcd" );
   
3.         map.put( "3", "def" );
   
4.         map.put( "4", "gg" );
   
5.         map.put( "12", "yy" );
   
6.         map.put( "23", "dx" );
   
7.         map.put( "34", "gwew" );
   
8.         map.put( "234", "wsgvw" );
   
9.         map.put( "123", "wsgvw" );
   
10.         map.put( "1234", "wsgvw" );
    

复制代码

也就是对于任意长度的组合，我们都可以分解，对于这道题，如果只求解组合个数，那么动态规划即可，思路就是从右往左，每次拆多少个字母组合，因为所有的组合都可拆，所以最简单的动态规划即可解决，比如还是上面的"1234"，动态规划过程为：

那么，DP的关系式就可以写出来了：

S[ i ] = S[ i - 1 ] + S[ i - 2 ] + .... +  S[ 1 ] + S[ 0 ]; ->A

这个等式还可以简化，注意S[ i - 1 ] =  S[ i - 2 ] + .... +  S[ 1 ] + S[ 0 ]，把这个直接带入到A里面：

S[ i ] = S[ i - 1 ] +  S[ i - 1 ] = 2 * S[ i - 1 ]; ->B

也就是说使用DP，时间复杂度可以从O(n ^ 2)简化到O(n)。

好像可以这是更优解？但是，这只是算出了组合总数，没有得到具体的组合有哪些，所以我们需要从右往左，用第一个关系式recovery所有的组合，那么这个过程必然是O(n^2)，从这里说明得到所有组合，必然不能优于O(n ^ 2)。但你给的原变种题比我给的变种题还有难，因为不是所有组合都能拆，也就是说运用上面的方法，每次拆分的时候，我们得检查是否测在这样得映射关系，如果有才能拆，如果没有则不能拆。加上这个思路，我们依然可以使用动态规划，现在拆解组合只有你原来给得哪些：

1.         map.put( "1", "abc" );
   
2.         map.put( "2", "bcd" );
   
3.         map.put( "3", "def" );
   
4.         map.put( "4", "gg" );
   
5.         map.put( "12", "yy" );
   
6.         map.put( "23", "dx" );
   
7.         map.put( "34", "gwew" );
   
8.         map.put( "234", "wsgvw" );
   

复制代码

那么动态规划得过程变为：

所以无论是求得组合总数，还是求得每个组合，我们都只能用A关系式，不能用B，这里得分析也证明应该不可能有更优解了，要得到所有组合，无论是不是给到所有可拆解组合，最优都必须在Ω(n^2)内完成。当然，这里assume所有映射关系都是unique，如果不是就更复杂了，也不能更快了。

不知道解决你得问题木有哇？有什么问题，可以随时追问哒~