Reverse Java String using Recursion technique
Problem Description :
Write a function that reverses a string. The input string is given as an array of characters s.
Example 1 :
Input: s = ['h', 'e', 'l', 'l', 'o']
Output: ['o','l','l','e','h]
Example 2 :
Input: s = ['H', 'a', 'n', 'n', 'a', 'h']
Output: ['h', 'a', 'n', 'n', 'a', 'H']
Lets see how we can solve this problem using recursion. Lets first understand about recursion :
What is Recursion?
Recursion is an approach to solving problems using a function that calls itself as a subroutine. Means we are calling same function over and over again until our base condition does not satisfy.
Each time a recursive function calls itself, it reduces the given problem into subproblems. The recursion call continues until it reaches a point where the subproblem can be solved without further recursion.
Solution 1 : Reverse string using Recursion with temp function
class Solution {
public static void reverseString(char[] s) {
tempFunction(0, s.length - 1, s);
}
public static void tempFunction(int start, int end, char[] array) {
if (start <= end) {
char temp = array[start];
array[start] = array[end];
array[end] = temp;
tempFunction(start+1, end-1, array);
}
}
}
Solution explanation :
- In reverseString method, we are calling tempFunction that taekes three arguments.
- Start of array (0)
- End of array (s.length - 1)
- Array
- In tempFunction if (start <= end) is our Base condition for recursion. Means we are calling tempfunction until start not become less then or equals to end.
- In if condition, we are swaping first and last element of array. and at last we call again tempFunction.
Output explanation :
char[] array = ['j', 'a', 'v', 'a', 'c', 'o', 'd', 'e']
- start = 0, end = 7
- start <= end | 0 <= 7 becomes true
- temp = j, array[0] = e, array[7] = j
- array = ['e', 'a', 'v', 'a', 'c', 'o', 'd', 'j']
- start = 1, end = 6, array = ['e', 'a', 'v', 'a', 'c', 'o', 'd', 'j']
- 1 <= 6 becomes true
- temp = a, array[1] = d, array[6] = a
- array = ['e', 'd', 'v', 'a', 'c', 'o', 'a', 'j']
- start = 2, end = 5, array = ['e', 'a', 'v', 'a', 'c', 'o', 'd', 'j']
- 2 <= 5 becomes true
- temp = v, array[2] = o, array[5] = v
- array = ['e', 'd', 'o', 'a', 'c', 'v', 'a', 'j']
- start = 3, end = 4, array = ['e', 'a', 'v', 'a', 'c', 'o', 'd', 'j']
- 3 <= 4 becomes true
- temp = a, array[3] = c, array[4] = a
- array = ['e', 'd', 'o', 'c', 'a', 'v', 'a', 'j']
- start = 4, end = 3, array = ['e', 'd', 'o', 'c', 'a', 'v', 'a', 'j']
- 4 <= 3 becomes false
We can also solve this problem without another function. we can using while loop for this. lets see solution for that.
Solution 2 : Reverse String using Recursion with While loop
class Solution {
public static void reverseString(char[] s) {
int start = 0;
int end = s.length-1;
char temp = 0;
while(start <= end) {
temp = s[start];
s[start++] = s[end];
s[end--] = temp;
}
}
}
Solution explanation :
Here, we are doing same thing but without new method. In while loop, we are checking our base condition. So until out base condition does not satisfy we are iterate through array and finally we get reverse string.
Happy Coding
See other problems and its solution in Java :
Comments
Post a Comment