[FIXED] Reverse string without affecting specific characters that user can input

Issue

Need to reverse string without affecting all non alphabetical charachters and specific characters that user can input to ignore. I figured out how to ignore non alphabetical characters and it do the job when text-to-reverse match text-to-ignore strings but don’t work when it different.
Here’s my code:

public class Anagram {

public static String reverseString(String rev, String ignore) {
    char[] str = rev.toCharArray();
    int r = str.length - 1;
    int l = 0;
    if ((ignore != null) && ignore.contains(rev)) {
        char[] ign = ignore.toCharArray();
        while (l < r)
            for (int i = 0; i < ignore.length(); i++) {
                if (!Character.isAlphabetic(str[l]) || (ign[i] == str[l])) {
                    l++;
                } else if (!Character.isAlphabetic(str[r]) || (ign[i] == str[r])) {
                    r--;
                } else {
                    char tmp = str[l];
                    str[l] = str[r];
                    str[r] = tmp;
                    l++;
                    r--;
                }
            }
    } else {
        while (l < r) {
            if (!Character.isAlphabetic(str[l])) {
                l++;
            } else if (!Character.isAlphabetic(str[r])) {
                r--;
            } else {
                char tmp = str[l];
                str[l] = str[r];
                str[r] = tmp;
                l++;
                r--;
            }
        }
    }
    return new String(str);
}}}

Example what i need:
Input: String rev "abcdefg", String ignore "cf"
Output: "gecdbfa"

Solution

In your code, when you swap values at 2 positions, they both have to be valid characters, meaning, both alphabetic and not of the characters of ignore. Second issue is you are equating a character of ignore directly with left pointer of the rev string in ign[i] == str[l]. They need not coincide index-wise this way.


Algorithm:

  • Create a set of all the characters in ignore.
  • Create a result array of type char with length same as rev.
  • Create another reserved boolean array with length same as rev.
  • Now, loop on rev char by char. If it is non-alphabetic or one of the chars of ignore, fix that position with that char. In reserved, mark this index as true as we can’t mess with this index now.
  • Once done, move again on the string rev from left to right and this time only consider alphabetic chars and the ones which aren’t a part of ignore. Now, add them in a reverse way inside result to actually store in the reversed state. Note that the next non-reserved location won’t always be sequential in nature with a simple ptr--. We would need a while loop inside to get the next non reserved seat and insert them there.

Snippet:

public static String reverseString(String rev, String ignore) {
  Set<Character> set = new HashSet<>();
  for(int i = 0; i < ignore.length(); ++i){
    set.add(ignore.charAt(i));
  }
  
  char[] result = new char[rev.length()];
  boolean[] reserved = new boolean[rev.length()];
  
  
  for(int i = 0; i < rev.length(); ++i){
    if(!Character.isAlphabetic(rev.charAt(i)) || set.contains(rev.charAt(i))){
      result[i] = rev.charAt(i);
      reserved[i] = true;
    }
  }
  
  int ptr = rev.length() - 1;
  for(int i = 0; i < rev.length(); ++i){
    if(Character.isAlphabetic(rev.charAt(i)) && !set.contains(rev.charAt(i))){
      while(ptr >= 0 && reserved[ptr]) ptr--;
      result[ptr--] = rev.charAt(i);
    }
  }
  
  return new String(result);
}

Online Demo

Answered By – nice_dev

Answer Checked By – David Marino (Easybugfix Volunteer)

Leave a Reply

(*) Required, Your email will not be published