我正在尝试使用递归找到给定字符串的等级

Question

我正在尝试使用递归来查找给定字符串的等级，但似乎无法按照我想要的方式从递归中得出。我要去哪里错了？

    class Solution {
    public static int flag=0;
    public static int ans=0;
    public static int findRank(String A) {
      /* write your solution here */
      char[] carr=A.toCharArray();
      Arrays.sort(carr);
      String suffix=new String(carr);
      ArrayList<String> list=new ArrayList<String>();
          int rank=0;
      rank=generate(rank,"",suffix,list,A);

      for(int i=0;i<list.size();i++)
        System.out.print(list.get(i)+" ");

       return rank;
     }

    public static int generate(int rank,String prefix,String suffix, ArrayList<String> list,String A){
        if(suffix.length()==0){
            list.add(prefix);
            rank++; 
            if(prefix.equals(A)){

                return rank;
            }
        }

        for(int i=0;i<suffix.length();i++) {
          //  System.out.println(rank);
          return generate(rank,prefix+suffix.charAt(i),suffix.substring(0,i)+suffix.substring(i+1),list, A); 
        }

        return rank;
    }
}

这是问题：给定一个字符串，请在按字典顺序排序的排列中找到该字符串的等级。假设没有重复字符。

示例：

输入：'acb'输出2字母“ a”，“ c”和“ b”的顺序排列：

abcACBbacbca出租车cba

我尝试将其放在可视化器中，这是该代码：

    import java.util.*;
public class Solution {
    public static int flag=0;
    public static int ans=0;
  public static void main(String args[]) {
      /* write your solution here */
     String A="dbca";
      char[] carr=A.toCharArray();
      Arrays.sort(carr);
      String suffix=new String(carr);
      ArrayList<String> list=new ArrayList<String>();
          int rank=0;
      rank=generate(rank,"",suffix,list,A);

      for(int i=0;i<list.size();i++)
        System.out.print(list.get(i)+" ");

       System.out.println(rank);

  }

    public static int generate(int rank,String prefix,String suffix, ArrayList<String> list,String A){
        if(suffix.length()==0){
            list.add(prefix);
            rank++;
            if(prefix.equals(A)){

                return rank;
            }

        }

            for(int i=0;i<suffix.length();i++){
              //  System.out.println(rank);
                   return generate(rank,prefix+suffix.charAt(i),suffix.substring(0,i)+suffix.substring(i+1),list, A);

            }

        return rank;
    }
}

https://cscircles.cemc.uwaterloo.ca/java_visualize/#mode=edit

Answer 1

您的for循环会导致您在找到第一个排列后结束递归，因此总是返回1。

您应该做的是一旦找到所需的排列，就结束递归。例如，如果您的递归方法将返回boolean标志而不是int，则可以这样做。

一旦递归方法返回，list的长度将是您要查找的等级：

public static int findRank(String A) 
{
    char[] carr=A.toCharArray();
    Arrays.sort(carr);
    String suffix=new String(carr);
    ArrayList<String> list=new ArrayList<String>();
    generate("",suffix,list,A);
    for(int i=0;i<list.size();i++)
        System.out.print(list.get(i)+" ");

     return list.size();
}

public static boolean generate(String prefix,String suffix, ArrayList<String> list,String A)
{
    if(suffix.length()==0){
        list.add(prefix);
        return (prefix.equals(A));
    }

    for(int i=0;i<suffix.length();i++) {
        if (generate(prefix+suffix.charAt(i),suffix.substring(0,i)+suffix.substring(i+1),list, A)) {
            return true;
        }
    }

    return false;
}