Palindrome is a string which which reads the same backward as forward. For example: kayak, rotor, madam, radar, civic etc.
There are various ways to check whether String is a palindrome:
1. Reverse the string and compare: In this approach, we reverse the string and compare it with original string. If these two strings are same, it proves that string is palindrome. Time Complexity of this algorithm is still O(n) but it requires 2n operations (n for reverse and n for comparison)
2. Split the string from middle, reverse second half: In this approach, we form another string by splitting original string from middle to end. After split, we reverse this splitted string. Now, we run a loop to compare original list up to middle element with string formed by split and reverse. If comparison is successful, string is palindrome. It requires n operations (n/2 for split-reverse and n/2 for comparison)
3. Use two pointers: This is the most efficient method out of these three. We take two pointers - one from start of the string and another from end of the string. First pointer moves forward whereas second pointer moves backwards. At every iteration, we check if both the pointers have same character in the string. If both are same, first pointer is moved forward and second pointer is moved backwards. If values are not same, we terminate the loop and declare that string is not a palindrome.
Loop continues until second pointer index becomes lower than first pointer index.
There are various ways to check whether String is a palindrome:
1. Reverse the string and compare: In this approach, we reverse the string and compare it with original string. If these two strings are same, it proves that string is palindrome. Time Complexity of this algorithm is still O(n) but it requires 2n operations (n for reverse and n for comparison)
2. Split the string from middle, reverse second half: In this approach, we form another string by splitting original string from middle to end. After split, we reverse this splitted string. Now, we run a loop to compare original list up to middle element with string formed by split and reverse. If comparison is successful, string is palindrome. It requires n operations (n/2 for split-reverse and n/2 for comparison)
3. Use two pointers: This is the most efficient method out of these three. We take two pointers - one from start of the string and another from end of the string. First pointer moves forward whereas second pointer moves backwards. At every iteration, we check if both the pointers have same character in the string. If both are same, first pointer is moved forward and second pointer is moved backwards. If values are not same, we terminate the loop and declare that string is not a palindrome.
Loop continues until second pointer index becomes lower than first pointer index.
No comments:
Post a Comment