Find a Palindromic String in the Array.

Given an array of strings words[], write a program to return the first palindromic string in the array. If there is no such palindromic string present in the given array then return an empty string "".

Palindromic strings are those strings that read the same from left to right and from right to left. Example: radar(alert-passed)

Example: 
Input: words[] = {"abc", "cap", "radar", "racecar", "cook"}
Output: radar
Explanation: The first palindromic string is "radar"

Input: words[] = {"pet", "cable", "code"}
Output: ""
Explanation: There is no palindromic string, so returning an empty string.

There are multiple approaches to solving this problem, let's discuss each of them one by one:

Approach 1: Brute Force Approach.

In this approach, we are going to check each string in the array one by one if it is a palindrome. If palindrome is found then return it, else return an empty string.

Below is C++ Implementation:

//C++ Program to find Palindromic String
#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool isPalindrome(string s) {
    int n = s.length();
    for (int i = 0; i < n / 2; i++) {
        if (s[i] != s[n - i - 1]) {
            return false;
        }
    }
    return true;
}

string firstPalindromicString(vector<string>& words) {
    for (string word : words) {
        if (isPalindrome(word)) {
            return word;
        }
    }
    return "";
}

int main() {
    vector<string> words = {"hello", "world", "racecar", "palindrome"};
    string result = firstPalindromicString(words);
    if (result == "") {
        cout << "No palindromic string found." << endl;
    } else {
        cout << "First palindromic string: " << result << endl;
    }
    return 0;
}

Output:

First palindromic string: racecar

Time Complexity: O(n * m^2), where n is the number of words in the array and m is the length of the longest word. This is because we need to check each word in the array, and for each word, we need to check if it is a palindrome, which takes O(m^2) time.
Space Complexity: O(1), since we are not using any additional space beyond the input array.

Approach 2: Using Two Pointers.

In this approach, we use two-pointers to compare characters from the beginning and end of each string. If the characters match, move the pointers inwards until they meet in the middle of the string. If the string is a palindrome, return it, otherwise move on to the next string in the array.

Below is C++ Implementation:

//C++ Code for finding Palindromic String
#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool isPalindrome(string s) {
    int i = 0, j = s.length() - 1;
    while (i < j) {
        if (s[i] != s[j]) {
            return false;
        }
        i++;
        j--;
    }
    return true;
}

string firstPalindromicString(vector<string>& words) {
    for (string word : words) {
        if (isPalindrome(word)) {
            return word;
        }
    }
    return "";
}

int main() {
    vector<string> words = {"hello", "world", "racecar", "palindrome"};
    string result = firstPalindromicString(words);
    if (result == "") {
        cout << "No palindromic string found." << endl;
    } else {
        cout << "First palindromic string: " << result << endl;
    }
    return 0;
}

Output:

First palindromic string: racecar

Time Complexity: O(n * m), where n is the number of words in the array and m is the length of the longest word. This is because we need to check each word in the array, and for each word, we need to compare each character from the beginning and end of the word, which takes O(m) time.
Space Complexity: O(1), since we are not using any additional space beyond the input array.

Approach 3: Using Reverse String.

This approach is to reverse each string in the array and compare it to the original string. If they are equal, the string is a palindrome. Return the first palindrome found, or an empty string if no palindrome is found.

Below is C++ Implementation:

//C++ Code for Palindromic String
#include <iostream>
#include <string>
#include <vector>

using namespace std;
//function to reverse each string
string reverseString(string s) {
    int n = s.length();
    for (int i = 0; i < n / 2; i++) {
        char temp = s[i];
        s[i] = s[n - i - 1];
        s[n - i - 1] = temp;
    }
    return s;
}

string firstPalindromicString(vector<string>& words) {
    for (string word : words) {
        if (word == reverseString(word)) {
            return word;
        }
    }
    return "";
}

int main() {
    //array of string
    vector<string> words = {"hello", "world", "racecar", "palindrome"};
    //function call
    string result = firstPalindromicString(words);
    
    if (result == "") {
        cout << "No palindromic string found." << endl;
    } else {
        cout << "First palindromic string: " << result << endl;
    }
    return 0;
}

Output:

First palindromic string: racecar

Time Complexity: O(n * m), where n is the number of words in the array and m is the length of the longest word. This is because we need to check each word in the array, and for each word, we need to reverse it, which takes O(m) time, and then compare it to the original word, which takes another O(m) time.
Space Complexity: O(1), since we are not using any additional space beyond the input array.

Find a Palindromic String in the Array.

No comments:

Post a Comment