1

给定一个字符串 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);
4

1 回答 1

0

您在这里有两个问题：

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);
    }
}
于 2019-11-05T08:52:43.520 回答