Tuesday, October 27, 2015

Reverse an array without affecting special characters


Given a string, that contains special character together with alphabets (‘a’ to ‘z’ and ‘A’ to ‘Z’), reverse the string in a way that special characters are not affected. e.g.

    Input:   str = "a,b$c"
    Output:  str = "c,b$a"
    Note that $ and , are not moved anywhere.  
    Only subsequence "abc" is reversed

    Input:   str = "Ab,c,de!$"
    Output:  str = "ed,c,bA!$"
     

Approach 1
 
public class Solution {  
   public static void main(String[] args) {  
     System.out.println(reverseString("man ish#"));  
   }  
   /**  
    * Reverse string with maintaining special character in place  
    *  
    * Algorithm:  
    * 1. create temporary array  
    * 2. copy all character from original array excluding special character  
    * 3. reverse the temporary array  
    * 4. start copying temporary array into original if element is an alphabetic character  
    * @param input  
    * @return  
    */  
   public static String reverseString(String input) {  
     char[] inputArr = input.toCharArray();  
     char[] tempArr = new char[input.length()];  
     int i=0;  
     int j=0;  
     for (char ch:inputArr){  
       if(Character.isAlphabetic(ch)){  
         tempArr[i] = ch;  
         i++;  
       }  
     }  
     i--;  
     while(j<i){  
       char temp = tempArr[i];  
       tempArr[i]= tempArr[j];  
       tempArr[j]=temp;  
       j++;  
       i--;  
     }  
     for(i=0,j=0;i<input.length();i++){  
       if(Character.isAlphabetic(inputArr[i])){  
         inputArr[i]= tempArr[j++];  
       }  
     }  
     return new String(inputArr);  
   }  
 }  
Approach 2
 
public class Solution {  
   public static void main(String[] args) {  
     System.out.println(reverseString("man ish#"));  
   }  
   /**  
    * Reverse a string with maintaining special character position.  
    * Algorithm :  
    * 1) Let input string be 'str[]' and length of string be 'n'  
    * 2) l = 0, r = n-1  
    * 3) While l is smaller than r, do following  
    * a) If str[l] is not an alphabetic character, do l++  
    * b) Else If str[r] is not an alphabetic character, do r--  
    * c) Else swap str[l] and str[r]  
    *  
    * @param input : Input string  
    * @return reverse string  
    */  
   public static String reverseString(String input) {  
     char[] inputArr = input.toCharArray();  
     int l = 0;  
     int r = inputArr.length - 1;  
     while (l < r) {  
       if (!Character.isAlphabetic(inputArr[l])) {  
         l++;  
       } else if (!Character.isAlphabetic(inputArr[r])) {  
         r--;  
       } else {  
         char tempChar = inputArr[l];  
         inputArr[l] = inputArr[r];  
         inputArr[r] = tempChar;  
         l++;  
         r--;  
       }  
     }  
     return new String(inputArr);  
   }  
 }  

2 comments: