java - 字符串的下一个字典顺序更大的排列

Question

问题是找到下一个比给定字符串更大的字符串 例如:输入:DKHC OP:HKDC。

我无法弄清楚我的代码哪里做错了。谁能帮我调试一下。

*

public static void main(String[] main)
    {
        String s = "gojh";
        String op="";
        //System.out.println();
        int i=s.length()-1;
        int j=i-1;
        boolean swapped=false;
        while(i>0)
        {
            j=i-1;
        while(j>=0)
        {   if(s.charAt(i)>s.charAt(j))
            {   System.out.println(s.charAt(j)+" ->"+s.charAt(i));
                s=s.substring(0,j)+s.charAt(i)+s.substring(j+1,i)+s.charAt(j)+s.substring(i+1);
                swapped=true;
                break;
            }
            else 
            {
                j--;
            }
        }
        System.out.println(i);
        if(swapped)
            break;
        else
            i--;

      } 
        //System.out.println(s);
        if((i-j)>=2)
           op= minimize(s,j);
        else
            op=s;
        System.out.println(op);
    }
    private static String minimize(String s,int index) {
        String reverse="";
        String original=s.substring(index+1);
        int i=original.length()-1;
        while(i>=0)
        {
            reverse=reverse+original.charAt(i);
            i--;
        }
        //System.out.println(reverse);

        return s.substring(0,index+1)+reverse;
    }

*

Answer 1

您的代码中没有给出 I/O 示例(代码的输入/输出和预期输出)，因此调试它过于详尽。但看一眼它就会告诉我一些事情:

1. 您实际上使用的是 O(n^2) 算法(n = 字符串长度)，而这很容易在一次迭代中解决。

2. 您的示例和问题描述有误。如果 i/p 是 DKHC , 下一个字典序更大的字符串是 HCDK并且不是 HKDC .

因此，假设你在那里犯了错误，我给你一个算法来做正确的事情(根据问题描述)。

• 从字符串的末尾开始。找到 charAt(i) < charAt(i+1) 所在的索引.停在那里。 (如果你没有得到这个条件并到达字符串的开头，给定的 i/p 已经是你可以获得的最大词汇排列。你可以在那里显示错误消息)
• 现在从头开始重复，找到一个索引j这样 charAt(i) < charAt(j) .您会一定会找到这样的索引。
• 在索引处交换字符 i和 j .
• 现在是最后(也是重要的) 步。从索引 i+1 反转整个字符串继续。