Thuật toán tìm dãy số Palindrome trong Java

Thuật toán tìm dãy số Palindrome trong Java có thể được thực hiện bằng cách kiểm tra xem một chuỗi có phải là chuỗi palindrome hay không. Một chuỗi palindrome là chuỗi đọc xuôi hay ngược đều như nhau, ví dụ như “racecar” hay “level”.

Thuật toán kiểm tra xem một chuỗi có phải là chuỗi palindrome hay không có thể được thực hiện như sau:

1. Tạo một biến boolean là isPalindrome và khởi tạo giá trị là true.
2. Lặp qua nửa đầu của chuỗi (từ đầu đến giữa) và kiểm tra xem ký tự đầu tiên có giống với ký tự ở vị trí tương ứng từ cuối chuỗi không. Nếu không giống, gán isPalindrome bằng false và thoát khỏi vòng lặp.
3. Nếu vòng lặp kết thúc mà isPalindrome vẫn giữ giá trị true, tức là chuỗi là chuỗi palindrome.

Dưới đây là mã nguồn Java thực hiện thuật toán trên:

public static boolean isPalindrome(String str) {
    boolean isPalindrome = true;
    int length = str.length();
    for (int i = 0; i < length / 2; i++) {
        if (str.charAt(i) != str.charAt(length - i - 1)) {
            isPalindrome = false;
            break;
        }
    }
    return isPalindrome;
}

Với hàm isPalindrome này, ta có thể kiểm tra xem một chuỗi có phải là chuỗi palindrome hay không bằng cách gọi hàm và truyền vào chuỗi cần kiểm tra. Hàm sẽ trả về giá trị true nếu chuỗi là chuỗi palindrome và false nếu không phải.

Đây là một ví dụ về cách tìm tất cả các chuỗi Palindrome trong một chuỗi đã cho bằng cách sử dụng thuật toán Brute Force trong Java:

public class PalindromeExample {

    public static void main(String[] args) {
        String input = "abaabcba";
        findAllPalindromes(input);
    }

    public static void findAllPalindromes(String input) {
        int n = input.length();

        // Duyệt qua tất cả các substring trong chuỗi
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                String sub = input.substring(i, j);
                if (isPalindrome(sub)) {
                    System.out.println(sub);
                }
            }
        }
    }

    public static boolean isPalindrome(String input) {
        int n = input.length();
        for (int i = 0; i < n / 2; i++) {
            if (input.charAt(i) != input.charAt(n - i - 1)) {
                return false;
            }
        }
        return true;
    }
}

Đầu vào của chương trình là chuỗi "abaabcba". Kết quả sẽ in ra tất cả các chuỗi Palindrome trong chuỗi này, bao gồm "a", "aa", "aba", "abcba", và "bcb".