String Manipulation Problems in Java

I have 开发者_运维问答the below 2 Problems asked yesterday in an interview

1> Given a string, compute a new string where identical chars that are adjacent in the original string are separated from each other by a "*".

Examples are as shown below::

function name is public String pairStar(String str)

 pairStar("hello") → "hel*lo"     
 pairStar("xxyy") → "x*xy*y"          
 pairStar("aaaa") → "a*a*a*a"

2> Given a string, compute a new string where all the lowercase 'x' chars have been moved to the end of the string.

Examples are as shown below::

function name is public String endX(String str)

endX("xxre") → "rexx"     
endX("xxhixx") → "hixxxx"     
endX("xhixhix") → "hihixxx"

Im not sure how to accomplish the given set of problems, and struggling how to solve this

For 1), here's a very straightforward regex way:

  String in = "helllo goodbye";
  String out = in.replaceAll("(.)(?=\\1)", "$1*");
  System.out.println(out);

Prints:

hel*l*lo go*odbye

Explanation:

(.)     //match any one character into group 1
(?=\\1) //positive lookahead for that same character by backreferencing group 1

$1*     //replace that one character with the character followed by *

I might take a crack at 2) later, but I don't like multiple questions wrapped into one.

Edit

Alright since I'm in a regex mood here's 2):

  String in = "xhixhix";
  String out = in;
  while (!out.matches("[^x]*x*")) {
     out = out.replaceAll("x(.*)", "$1x");
  }
  System.out.println(out);

This replaces x(something) with (something)x until all the xs are at the end of the string. I'm sure that there's a better way of doing this one with/than regex though.

In the first case you can iterate through the string keeping track of the previous character and comparing it to the current. Use a StringBuilder to build the new String.

In the second, iterate through, using two string builders (one for characters other than x, one for x), combine them at the end.

This is just off the top of my head in 30 seconds, and is the simplest approach. The second thought is that I'd prob use a regular expression, now that I think about it for 10 more seconds :)

Maybe I have misunderstood the question but if not if seems pretty simple. Your method could be something like for number 1:

public String pairStar(String s) {
    StringBuilder answer = new StringBuilder();
    char lastChar = s.charAt(0);
    answer.append(lastChar);

    for (int i = 1; i < s.length(); i++) {
        char currentChar = s.charAt(i);

        if (currentChar == lastChar) {
             answer.append("*");
        }
        answer.append(currentChar);
        lastChar = currentChar;
    }
    return answer.toString();
}

for the second one:

Loop through the string copying all the non lowercase x's into a new string while keeping count of the x's. At the end, just add the relevant number of x's to produce the final string.

public String endX(String str)
{
    StringBuilder s = new StringBuilder();
    int x = 0;

    for (int i = 0; i < str.length(); ++i)
    {
        if (str.charAt(i) == 'x')
        {
            ++x;
        }
        else
        {
            s.append(str.charAt(i));
        }
    }

    for (int i = 0; i < x; ++i)
    {
        s.append('x');
    }

    return s.toString();
}

for 1 you need a state machine with two states: (a) different from previous and (b) same as previous. starting state is (a). for each letter, you have to check in which state you are, output a character and change state accordingly. for each letter read in state (b), you also output a '*'.

for 2 you need an array in which you can shift elements left, and push at the end. 1. push a monitor token at the end (useful for halting condition) 2. iterate over all letters: when finding an "x", shift all elements left, push the x at the end and count the amount of x's you have seen. 3. stop when seeing the monitor token

I usually start problems like this with psuedo code, then move to the actual implementation.

For problem 1, here's how the psuedo code in my head works

for each character in the input string{
 if the previous character is the same{
  append a star to output string
 }
 append the character to the output string
}

For problem 2

for each character in the input string{
  if character is an x{
   increment x counter
  } else {
   append the character to the output string
  }
}
x counter times{
  append x to the output string
}

for the first problem :

public class StreamGobbler {

    public static void main(String[] a) {

        String s = "xxyy";

        StringBuffer sb = new StringBuffer(s);

        for(int i=0; i < sb.length()-1; i++) {
            if(sb.charAt(i) == sb.charAt(i+1)) {
                sb.insert(i+1, "*");
                i++;
            }
        }

        System.out.println(sb.toString());
    }
}

prints : x*xy*y

for your first problem

public String pairStar(String str){
        StringBuilder sb = new StringBuilder(str);
        for (int i = 0; i < sb.length()-1; i++) {
            if(sb.charAt(i)==sb.charAt(i+1)){
                sb.insert(++i, '*');
            }
        }
        return sb.toString();
    }

and for your second problem

public String endX(String str){
        StringBuilder sb = new StringBuilder(str);
        int length = sb.length()-1;
        for (int i = 0; i < length; i++) {
            if(sb.charAt(i)=='x'){
                sb.deleteCharAt(i--);
                sb.append('x');
                length--;
            }
        }
        return sb.toString();
    }

public class IdenticalChars {

    /**
     * separates any two same n adjacent characters of any string
     * by a * 
     */
    public static void main(String[] args) {
        StringBuilder sb=new StringBuilder();
        String s="aaabcgghelllloii";
        for(int i=0;i+1<s.length();i++){
            if((s.charAt(i)!=s.charAt(i+1)&&(i==0))){
                sb.append(s.charAt(i)+" "+s.charAt(i+1));
                //System.out.println(sb.toString());
            }
            else if((s.charAt(i)!=s.charAt(i+1)&&(i>0))){
                sb.append(s.charAt(i+1));
            }
            else if((s.charAt(i)==s.charAt(i+1))&&(i>0)){
                sb.append("*"+s.charAt(i+1));

            }
            else if((s.charAt(i)==s.charAt(i+1))&&(i==0)){
                sb.append(s.charAt(i)+"*"+s.charAt(i+1));
                }
        }

        System.out.println(sb.toString());
    }

}

output::a*a*abcg*ghel*l*l*loi*i

step 1. Tell them to shove it and then use python instead!

step 2.:

>>> strin = 'thixs ixs xan XArbitrarxy Stxrxing'
>>> xcnt = strin.count('x')
>>> result = ''.join(i for i in strin if i != 'x')
>>> result = result + ('x' * xcnt)
>>> print result
this is an XArbitrary Stringxxxxxx

These can be completed with recursion.

The first one breaks when the str length reaches 0. Otherwise it checks whether the current and next chars are the same and it they are it returns the current char with a "*" string. Else it just grabs the current string and loops back through. 1)

public String pairStar(String str) {
  int i = 0;
  if (str.length() == 0)
    return str;
  else if (str.length()-1 > i && str.charAt(i) == str.charAt(i+1))
    return str.charAt(i) + "*" + pairStar(str.substring(i+1));
  return str.charAt(i) + pairStar(str.substring(i+1));
} 

This also breaks when the str length is 0. Otherwise if the str character is a 'x' then loop through while holding a 'x' char in memory. Else grab the current char, and finally place the 'x' in memory at the end.

public String endX(String str) {
  int i = 0;
  if (str.length() == 0)
    return str;
  else if (str.charAt(i) == 'x')
    return endX(str.substring(i+1)) + 'x' ;
  return str.charAt(i) + endX(str.substring(i+1));
}

Here is one simple answer using recursion :)

public String pairStar(String str) {
     if(str.isEmpty())return ""; // our exit condition for recursion
     String sub1 = str.substring(0,1); // take the first char
     String sub2 = ""; 
     if(str.length()>1)sub2 = str.substring(1,2); // take second char if it it contains at least 2 chars
     if(sub1.equals(sub2)) return sub1+"*"+pairStar(str.substring(1)); //if two chars are equal putting star between
     return sub1 + pairStar(str.substring(1));//else continue as usual 
}