Java查找字符串的所有排列

忘是亡心i 2023-10-04 08:34 21阅读 0赞

为了解决这个问题，我们需要了解回溯的概念。

根据回溯算法：

*  将角色固定在第一个位置，然后将其余字符替换为第一个字符。像在ABC中一样，在第一次迭代中，通过分别将A与A，B和C交换来形成三个字符串：ABC，BAC和CBA。
 *  对其余字符重复步骤1，例如固定第二个字符B，依此类推。
 *  现在再次交换以返回到先前的位置。例如，从ABC，我们通过再次固定B来形成ABC，然后回溯到先前的位置并与C交换B。因此，现在我们有了ABC和ACB。
 *  对BAC和CBA重复这些步骤，以获取所有排列。

![20210317160108278.gif][]

#### 算法 ####

1.  定义一个字符串。
2.  修复角色并交换其余角色。
3.  调用其余字符的generatePermutation（）。
4.  回溯并再次交换字符。

#### 解决方案 ####

package Permutations;
    
    public class PermuteString {
    	// Function for generating different permutations of the string
    	public static void generatePermutation(String str, int start, int end) {
    		// Prints the permutations
    		if (start == end - 1)
    			System.out.println(str);
    		else {
    			for (int i = start; i < end; i++) {
    				// Swapping the string by fixing a character
    				str = swapString(str, start, i);
    				// Recursively calling function generatePermutation() for rest of the characters
    				generatePermutation(str, start + 1, end);
    				// Backtracking and swapping the characters again.
    				str = swapString(str, start, i);
    			}
    		}
    	}
    
    	// Function for swapping the characters at position I with character at position
    	// j
    	public static String swapString(String a, int i, int j) {
    		char[] b = a.toCharArray();
    		char ch;
    		ch = b[i];
    		b[i] = b[j];
    		b[j] = ch;
    		return String.valueOf(b);
    	}
    
    	public static void main(String[] args) {
    		String str = "ABC";
    		int len = str.length();
    		System.out.println("All the permutations of the string are: ");
    		generatePermutation(str, 0, len);
    	}
    }

[20210317160108278.gif]: https://img-blog.csdnimg.cn/20210317160108278.gif