Given a string. the task is to check if the string is symmetrical and palindrome or not. A string is said to be symmetrical if both the halves of the string are the same and a string is said to be a palindrome string if one half of the string is the reverse of the other half or if a string appears same when read forward or backward.
Example:
Input: khokho Output: The entered string is symmetrical The entered string is not palindrome Input:amaama Output: The entered string is symmetrical The entered string is palindrome
Approach 1: The approach is very naive. In the case of palindrome, a loop is run to the mid of the string and the first and last characters are matched. If the characters are not similar then the loop breaks and the string is not palindrome otherwise the string is a palindrome. In the case of symmetry, if the string length is even then the string is broken into two halves and the loop is run, checking the characters of the strings of both the half. If the characters are not similar then the loops break and the string is not symmetrical otherwise the string is symmetrical. If the string length is odd then the string is broken into two halves in such a way that the middle element is left unchecked, and the above same step is repeated.
Below is the implementation.
Python3
# Python program to demonstrate# symmetry and palindrome of the# string# Function to check whether the# string is palindrome or notdef palindrome(a): # finding the mid, start # and last index of the string mid = (len(a)-1)//2 #you can remove the -1 or you add <= sign in line 21 start = 0 #so that you can compare the middle elements also. last = len(a)-1 flag = 0 # A loop till the mid of the # string while(start <= mid): # comparing letters from right # from the letters from left if (a[start]== a[last]): start += 1 last -= 1 else: flag = 1 break; # Checking the flag variable to # check if the string is palindrome # or not if flag == 0: print("The entered string is palindrome") else: print("The entered string is not palindrome") # Function to check whether the# string is symmetrical or not def symmetry(a): n = len(a) flag = 0 # Check if the string's length # is odd or even if n%2: mid = n//2 +1 else: mid = n//2 start1 = 0 start2 = mid while(start1 < mid and start2 < n): if (a[start1]== a[start2]): start1 = start1 + 1 start2 = start2 + 1 else: flag = 1 break # Checking the flag variable to # check if the string is symmetrical # or not if flag == 0: print("The entered string is symmetrical") else: print("The entered string is not symmetrical") # Driver codestring = 'amaama'palindrome(string)symmetry(string) |
The entered string is palindrome The entered string is symmetrical
Time Complexity: O(n)
Auxiliary Space: O(n), where n is number of characters in string.
Approach 2:
We use slicing in this method.
Python3
string = 'amaama'half = int(len(string) / 2)first_str = string[:half]second_str = string[half:]# symmetricif first_str == second_str: print(string, 'string is symmetrical')else: print(string, 'string is not symmetrical')# palindromeif first_str == second_str[::-1]: # ''.join(reversed(second_str)) [slower] print(string, 'string is palindrome')else: print(string, 'string is not palindrome') |
amaama string is symmetrical amaama string is palindrome
The Time and Space Complexity for all the methods are the same:
Time Complexity: O(n)
Auxiliary Space: O(n)
METHOD 3:Using re module
APPROACH:
In the above code, we first check if the string is symmetrical or not using slicing. Then, we use the re.match function to match the pattern of the string with a regular expression that matches one or more word characters and ensures that the string ends there. Finally, we check if the original string is equal to its reversed version to determine if it’s a palindrome or not.
ALGORITHM:
1.Define a string input_str to be checked for symmetry and palindrome
2.Reverse the input_str using string slicing and store it in reversed_str
3.Check if the input_str and reversed_str are equal to each other. If yes, then the input_str is symmetrical
4.Use a loop to iterate through the input_str and compare the characters with the corresponding characters in the reversed_str. If any character does not match, then the string is not symmetrical
5.Use recursion to check if the string is symmetrical. If the length of the string is less than 2 or the first and last characters of the string are not the same, then return False. Otherwise, call the function recursively with the substring obtained by removing the first and last characters of the original string
6.Use built-in functions and regular expressions to check if the input_str is palindrome or not. The re.match function is used to match the pattern of the string with a regular expression that matches one or more word characters and ensures that the string ends there.
Python3
# Python program to check whether the string is Symmetrical or Palindromeimport reinput_str = "amaama"reversed_str = input_str[::-1]if input_str == reversed_str: print("The entered string is symmetrical")else: print("The entered string is not symmetrical")if re.match("^(\w+)\Z", input_str) and input_str == input_str[::-1]: print("The entered string is palindrome")else: print("The entered string is not palindrome") |
The entered string is symmetrical The entered string is palindrome
Time complexity: The time complexity of the program is O(n), where n is the length of the input string. This is because the program performs a single pass over the string to reverse it, and then checks if the reversed string is equal to the original string, and also checks if the original string is a palindrome using regex.
Space complexity: The space complexity of the program is O(n), where n is the length of the input string. This is because the program creates a new string to store the reversed input string, and also uses regex to check for palindrome, which may require additional memory for regex matching.
APPROACH 4:
we can check the strings whether it is palindrome or not by using the reversed() function to the string which reverses the string which makes us easy to write the program.
Python3
# codestring ="malayalam"print("the string is palindrome" if string==reversed(string) else "the string is not palindrome") |
Output:
the string is palindrome
