粉车店面

N个string合并成一个，要保留原来string里面字符的顺序。求所有可能组合
merge(['AB', 'C']) => ['ABC', 'ACB', 'CAB']
merge(['AB', 'CD']) => ['ABCD', 'ACBD', 'ACDB', 'CABD', 'CADB

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

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

补充内容 (2019-2-26 14:27):
用recursive + cache 解决。估计用iterative DP也行

两个string里可能有相同的字母吗

Goto 发表于 2019-2-26 15:45
两个string里可能有相同的字母吗

没问。估计可以有。如果有相同字母的话，结果会有duplicates，没关系

Backtracking做。每次从其中一个string取出一个。
去重的话，需要HashSet或Hashtable。

这个要track每个括号里的位置吧

因为顺序不能变 所以每次从任意一个string里面取一个 直到取完为止

总数量可以用组合数计算 比如最后一个
AB CD E
先从5个位置选两个 再从三个选两个
一共30种情况

大概写了下Backtracking
test了几个case 应该work

1. List<String> result = new ArrayList<>();
   
2.    
   
3.     public List<String> mergeStrings(List<String> strList){
   
4.         int len = 0;
   
5.         for(String str: strList) len+=str.length();
   
6.         int[] strIdx = new int[strList.size()];
   
7.         backtracking(len, strList, strIdx, "");
   
8.         return result;
   
9.     }
   
10. 
    
11.     public void backtracking(int len, List<String> strList, int[] strIdx, String path){
    
12.         if(len == 0){
    
13.             result.add(path);
    
14.             return;
    
15.         }
    
16. 
    
17.         for(int i = 0; i<strIdx.length; i++){
    
18.             if(strIdx[i]<strList.get(i).length()){
    
19.                 char c = strList.get(i).charAt(strIdx[i]);
    
20.                 strIdx[i]++;
    
21.                 backtracking(len-1, strList, strIdx, path+c);
    
22.                 strIdx[i]--;
    
23.             }
    
24.         }
    
25.     }

复制代码

Fustang 发表于 2019-5-12 21:35
大概写了下Backtracking
test了几个case 应该work

不用cache？