приклад 1:

// Java program to check whether a // string is a Palindrome // Using two pointing variables // Main class public class GFG { // Method // Returning true if string is palindrome static boolean isPalindrome(String str) { // Pointers pointing to the beginning // and the end of the string int i = 0, j = str.length() - 1; // While there are characters to compare while (i < j) { // If there is a mismatch if (str.charAt(i) != str.charAt(j)) return false; // Increment first pointer and // decrement the other i++; j--; } // Given string is a palindrome return true; } // Method 2 // main driver method public static void main(String[] args) { // Input string String str = 'geeks'; // Convert the string to lowercase str = str.toLowerCase(); // passing bool function till holding true if (isPalindrome(str)) // It is a palindrome System.out.print('Yes'); else // Not a palindrome System.out.print('No'); } }>

No>

Складність описаного вище способу:

Часова складність: Часова складність заданого коду дорівнює O(n), де n — довжина вхідного рядка. Це тому, що цикл while повторює половину рядка, щоб перевірити, чи є він паліндромом. Оскільки ми перевіряємо лише половину рядка, кількість ітерацій пропорційна n/2, що дорівнює O(n).

Космічна складність: Складність простору коду дорівнює O(1), оскільки код використовує лише постійну кількість додаткового простору, яка не залежить від розміру вхідних даних. У коді використовуються лише змінні i, j і str, кожна з яких займає постійну кількість місця. У коді не створюється додатковий простір.

приклад 2:

// Java Program to check Whether // the String is Palindrome // or Not // Main class class GFG { // Method 1 // Returns true if string is a palindrome static boolean isPalindrome(String str) { // Pointers pointing to the beginning // and the end of the string int i = 0, j = str.length() - 1; // While there are characters to compare while (i < j) { // If there is a mismatch if (str.charAt(i) != str.charAt(j)) return false; // Increment first pointer and // decrement the other i++; j--; } // Given string is a palindrome return true; } // Main driver method public static void main(String[] args) { String str = 'geeks'; String str2 = 'RACEcar'; // Change strings to lowercase str = str.toLowerCase(); str2 = str2.toLowerCase(); // For string 1 System.out.print('String 1 :'); if (isPalindrome(str)) System.out.print('It is a palindrome'); else System.out.print('It is not a palindrome'); // new line for better readability System.out.println(); // For string 2 System.out.print('String 2 :'); if (isPalindrome(str2)) System.out.print('It is a palindrome'); else System.out.print('It is not a palindrome'); } }>

String 1 :It is not a palindrome String 2 :It is a palindrome>

Складність описаного вище способу:

Часова складність: Часова складність заданого коду дорівнює O(n), де n — довжина вхідного рядка. Це тому, що цикл while у методі `isPalindrome` повторює половину рядка, щоб перевірити, чи є він паліндромом. Оскільки ми перевіряємо лише половину рядка, кількість ітерацій пропорційна n/2, що дорівнює O(n).

Космічна складність: Складність простору коду дорівнює O(1), оскільки код використовує лише постійну кількість додаткового простору, яка не залежить від розміру вхідних даних. У коді використовуються лише змінні i, j, str і str2, кожна з яких займає постійну кількість місця. У коді не створюється додатковий простір.

3. Рекурсивний підхід для P Програма alindrome на Java

Підхід дуже простий. Подібно до підходу з двома покажчиками, ми перевіримо перше та останнє значення рядка, але цього разу це буде через рекурсію.

машинопис дата час

• Ми візьмемо два покажчики i, що вказують на початок рядка, і j, що вказує на кінець рядка.
• Продовжуйте збільшувати i та зменшувати j, поки i
• Перевірте, чи однакові символи на цих покажчиках. Ми робимо це за допомогою рекурсії – (i+1, j-1
• Якщо всі символи однакові в i-му та j-му індексах, доки не буде виконано умову i>=j, вивести true else false.

Нижче наведено реалізацію вищезазначеного підходу:

// Java program to check whether a // string is a Palindrome using recursion import java.io.*; // Driver Class class GFG { public static boolean isPalindrome(int i, int j, String A) { // comparing the two pointers if (i>= j) { return true; } // порівняння символів у цих покажчиках if (A.charAt(i) != A.charAt(j)) { return false; } // перевірка всього ще раз рекурсивно return isPalindrome(i + 1, j - 1, A); } public static boolean isPalindrome(String A) { return isPalindrome(0, A.length() - 1, A); } // основна функція public static void main(String[] args) { // Вхідний рядок String A = 'geeks'; // Перетворення рядка на нижній регістр A = A.toLowerCase(); логічний str = isPalindrome(A); System.out.println(str); } }>

false>

Складність описаного вище способу:

Часова складність: Часова складність заданого коду дорівнює O(n), де n — довжина вхідного рядка. Це пояснюється тим, що функція isPalindrome рекурсивно викликає себе для символів у позиціях (i+1, j-1), доки покажчики i та j не перетнуться один з одним або символи в покажчиках не будуть рівними. Оскільки ми порівнюємо кожен символ у рядку рівно один раз, часова складність дорівнює O(n).

Космічна складність: Просторова складність коду дорівнює O(n), де n - довжина вхідного рядка. Це пояснюється тим, що кожен рекурсивний виклик створює новий фрейм стека, який зберігає поточні значення параметрів функції та локальних змінних. У гіршому випадку стек викликів функцій може зрости до n/2 (коли вхідний рядок є паліндромом), тому складність простору становить O(n).

4. Використання підходу StringBuilder в Java

У цьому підході

наскільки великий екран мого комп'ютера

• По-перше, ми приймаємо рядок, введений користувачем.
• Потім ми створюємо об’єкт Stringbuilder str1″і зберігаємо в ньому значення String.
• Метод reverse() у Stringbuider дає нам зворотний рядок. Зберігайте цей зворотний рядок у str1.
• За допомогою методу equals() ми порівнюємо значення рядка, за допомогою умов if і else перевіряємо, схоже значення рядка чи ні.

Нижче наведено реалізацію вищезазначеного підходу:

import java.util.Scanner; public class Main { public static void main(String[] args) { String str = 'GeeksForGeeks'; // String for testing StringBuilder str1 = new StringBuilder(str); str1.reverse(); if (str.equals(str1.toString())) { System.out.println('Palindrome String'); } else { System.out.println('Not a palindrome String'); } } }>

Not a palindrome String>

Складність наведеного вище коду:

Часова складність: Часова складність коду дорівнює O(n), де n знову є довжиною вхідного рядка str. Основним фактором, що сприяє цій часовій складності, є реверсування рядка за допомогою str1.reverse(). Реверсування рядка таким чином має часову складність O(n), де n — довжина рядка. Інші операції в коді, такі як читання вхідних даних і порівняння рядків, є операціями з постійним часом і істотно не впливають на загальну часову складність.

Космічна складність: Просторова складність заданого коду Java дорівнює O(n), де n — довжина вхідного рядка str. Це пояснюється тим, що код використовує StringBuilder для зберігання перевернутої копії вхідного рядка, а простір, необхідний для StringBuilder, пропорційний довжині вхідного рядка.

довідка

Щоб дізнатися більше про Palindrome, див Програма для String Palindrome .