java - 使用 arraylist 打印给定字符串中长度为 k 的所有可能的字符串，并允许重复

Question

给定一个字符串 S 和一个整数 k，您需要查找并返回仅使用字符串 S 中存在的字符即可组成 k 大小的所有可能字符串。 这些字符可以根据需要重复多次。

import java.util.*;
public class Solution {
    public static String[] allStrings(String charSet, int len) {    
        // Write your code here 
        HashMap<Character,Boolean> map=new HashMap<>();
        for (int i=0; i<charSet.length();i++){
            if(!map.containsKey(charSet.charAt(i))){
                map.put(charSet.charAt(i),true);
            }
        }
        ArrayList<Character> al=new ArrayList<Character>();
        for (Map.Entry<Character,Boolean> entry:map.entrySet()){
            al.add(entry.getKey());
        }
        ArrayList<String> real=new ArrayList<String>();
        String pre="";
        perm(pre,al,len,real);
        String []a=new String[real.size()];
        a=real.toArray(a);
        return a;
    }

    public static void perm(String pre,ArrayList<Character> al,int k,ArrayList<String> real) {
        if(k==0){
            real.add(pre);
            return;
        }
        for(int i=0;i<al.size();i++){   
            pre=pre+al.get(i);
            perm(pre,al,--k,real);
        }
    }
}

这里我收到堆栈溢出错误@

pre=pre+al.get(i);
perm(pre,al,--k,real);

Answer 1

您这里有两个问题:

pre=pre+al.get(i);
perm(pre,al,--k,real);

1. 您进行此递归调用 al.size()次，每次递减 k 。自 k初始化为所需的长度 String s，如果k < al.size() ，它最终会变成负数，并且递归调用永远不会终止(因为它仅在 k==0 时终止)。

2. 在每次递归调用之前，您将一个字符添加到 pre ，但您不会删除上一次迭代中添加的字符。因此你最终会得到输出 String s 比所需长度长。

您可以按如下方式修复问题，但保留 pre和k不变:

public static void perm(String pre,ArrayList<Character> al,int k,ArrayList<String> real)
{
    if(k==0){
        real.add(pre);
        return;
    }
    for(int i=0;i<al.size();i++){
        perm(pre+al.get(i),al,k-1,real);
    }
}