Cách tìm tất cả hoán vị của chuỗi Java [Có code mẫu]

Reading Time: 2 minutes

Trong hướng dẫn này, chúng ta sẽ học cách tìm tất cả hoán vị của chuỗi Java. Đây là một câu hỏi “mẹo” thường xuất hiện trong các buổi phỏng vấn Java.

Thuật toán tạo hoán vị cho String trong Java

Chúng ta sẽ bắt đầu bằng cách lấy ký tự đầu tiên của chuỗi và hoán vị phần còn lại.

Ví dụ, nếu chuỗi là "ABC" thì:

• Ký tự đầu tiên là A
• Các hoán vị của phần còn lại ("BC") là "BC" và "CB"

Sau đó, ta chèn ký tự đầu tiên vào tất cả các vị trí có thể trong từng hoán vị con:

• "BC" → "ABC", "BAC", "BCA"
• "CB" → "ACB", "CAB", "CBA"

Chúng ta có thể viết một hàm đệ quy để trả về các hoán vị của phần chuỗi còn lại, sau đó viết thêm một hàm khác để chèn ký tự đầu tiên vào tất cả các vị trí có thể trong các hoán vị đó, nhằm tạo ra danh sách đầy đủ các hoán vị của chuỗi ban đầu.

Chương trình Java để in ra tất cả hoán vị của String

package com.journaldev.java.string;

import java.util.HashSet;
import java.util.Set;

/**
 * Java Program to find all permutations of a String
 * @author Pankaj
 *
 */
public class StringFindAllPermutations {
    public static Set<String> permutationFinder(String str) {
        Set<String> perm = new HashSet<String>();
        //Handling error scenarios
        if (str == null) {
            return null;
        } else if (str.length() == 0) {
            perm.add("");
            return perm;
        }
        char initial = str.charAt(0); // first character
        String rem = str.substring(1); // Full string without first character
        Set<String> words = permutationFinder(rem);
        for (String strNew : words) {
            for (int i = 0;i<=strNew.length();i++){
                perm.add(charInsert(strNew, initial, i));
            }
        }
        return perm;
    }

    public static String charInsert(String str, char c, int j) {
        String begin = str.substring(0, j);
        String end = str.substring(j);
        return begin + c + end;
    }

    public static void main(String[] args) {
        String s = "AAC";
        String s1 = "ABC";
        String s2 = "ABCD";
        System.out.println("\\nPermutations for " + s + " are: \\n" + permutationFinder(s));
        System.out.println("\\nPermutations for " + s1 + " are: \\n" + permutationFinder(s1));
        System.out.println("\\nPermutations for " + s2 + " are: \\n" + permutationFinder(s2));
    }
}

Tôi đã sử dụng Set để lưu trữ các hoán vị của chuỗi, nhằm tự động loại bỏ các giá trị trùng lặp.

Kết quả đầu ra

Permutations for AAC are: 
[AAC, ACA, CAA]

Permutations for ABC are: 
[ACB, ABC, BCA, CBA, CAB, BAC]

Permutations for ABCD are: 
[DABC, CADB, BCAD, DBAC, BACD, ABCD, ABDC, DCBA, ADBC, ADCB, CBDA, CBAD, DACB, ACBD, CDBA, CDAB, DCAB, ACDB, DBCA, BDAC, CABD, BADC, BCDA, BDCA]

Vậy là chúng ta đã hoàn thành việc tìm tất cả các hoán vị của String trong Java.