String

public class ReplaceSpaceInString {
  private static char[] replaceSpaceInString(char[] str, int length) {
    int spaceCounter = 0;

    //First lets calculate number of spaces
    for (int i = 0; i < length; i++) {
      if (str[i] == ' ') 
        spaceCounter++;
    }

    //calculate new size
    int newLength = length + 2*spaceCounter;

    char[] newArray = new char[newLength+1];
    newArray[newLength] = '\0';

    int newArrayPosition = 0;

    for (int i = 0; i < length; i++) {
      if (str[i] == ' ') {
        newArray[newArrayPosition] = '%';
    newArray[newArrayPosition+1] = '2';
    newArray[newArrayPosition+2] = '0';
    newArrayPosition = newArrayPosition + 3;
      }
      else {
    newArray[newArrayPosition] = str[i];
    newArrayPosition++;
      }
    }               
    return newArray;
  }

  public static void main(String[] args) {
    char[] array = {'a','b','c','d',' ','e','f','g',' ','h',' ','j'};
    System.out.println(replaceSpaceInString(array, array.length));
  }
}

 public class Test {
public void replaseSpaces(str) {
    str = str.replaceAll(" ","%20");
    System.out.println(str);
}

public static void main(String[] args) {
    Test tst = new Test();
   String str = "the dog  ";
   tst.replaseSpaces(str, length);  
}

}

one more thing you can change Character Array to String and String to Character Array –

 char[] ch =str.toCharArray();
 ch.toString()

Replace Blanks in a String

Images Question 9 Please implement a function to replace each blank in a string with “%20”. For instance, it outputs “We%20are%20happy.” if the input is “We are happy.”.

If a URL parameter contains some special characters in web programming, such as blanks and ‘#’s, it may block servers from retrieving correct parameter information. Therefore, it is necessary to convert these characters into strings understandable by servers. The conversion rule is to append the ASCII value of a special character to a ‘%’. For example, the ASCII value for a blank is 32, 0x20 in hexadecimal, so a blank is converted to “%20”. Take ‘#’ as another example: its ASCII value is 35, 0x23 in hexadecimal, so it is replaced with “%23”.

There are library methods to replace a piece of string with another, such as String.Replace in C# and String.replaceAllin Java. However, usually it is not the interviewers’ intention to ask candidates to just call existing methods in libraries. They are more interested to know whether candidates have the ability to implement the replacement functionality.

A string with blanks will become longer if each blank is replaced with three characters: ‘%’, ‘2’, and ‘0’. If the replacement is on the original string, the longer converted string may overlap with memory behind the string. If it is allowed to create a new string and replace blanks on the new string, we can allocate enough memory to accommodate the longer converted string. Since there are two options, candidates should ask interviewers to clarify their requirements. Let’s suppose the requirement is to replace blanks on the original string, and there is enough vacant memory behind it.

Replace from Left to Right in O(n2) Time

An intuitive solution is to scan a string from beginning to end and replace each blank when it is met. Because a character is replaced with three, we must move characters behind blanks; otherwise, two characters will be overlapped.

Let’s take a string “We are happy.” as an example. We employ grids to visualize characters in a string, as shown in Figure 3-3(a).

When the first blank is replaced, the string becomes the content of Figure 3-3(b). We have to move the characters in the area in the light gray background. When the second blank is replaced, it becomes the content in Figure 3-3(c). Note that characters in “happy.” are moved twice.

images

Figure 3-3. Replace every blank in “We are happy.” with “%20” from left to right. (a) This is the original string, “We are happy.”. (b) Replace the first blank with “%20”. It requires you to move characters with the light gray background. (c) Replace the second blank with “%20”. It requires you to move characters with the dark gray background again.

Supposing the length of the string is n. O(n) characters are moved for each blank, so the total time efficiency is O(n2) to replace O(n) blanks.

Interviewers may not be satisfied when they are told of this solution. What they expect is a more efficient solution. In the previous analysis, there are many characters moved multiple times. Is it possible to reduce the number of movements? Fortunately, the answer is yes. Let’s have a try by replacing blanks from the end to the beginning.

Replace from Right to Left in O(n) Time

The number of blanks in the original string is gotten when it is scanned, and then the length of the converted string can also be gotten. The length increases by two when a blank is replaced, so the length after conversion is obtained by adding the original length to double the number of blanks. Take the string “We are happy.” as an example again. Its length is 14 (including ‘\0’), and the length of the replaced string is 18 since there are two blanks in the original string.

Characters are copied or replaced from right to left at this time. Two pointers, P1 and P2, are declared. P1 is initialized to the end of original string, and P2 is initialized to the end of replaced string, as shown in Figure 3-4(a). The character pointed to by P1 is copied to where P2 points, and both pointers are moved backward until P1 points to a blank (Figure 3-4(b)). Characters with the light gray background are copied.

Note that all characters are copied (moved) once at most, so its time efficiency is O(n) and it is faster than the first solution.

It is time to implement code when your solution is accepted by interviewers. Some sample code is shown in Listing 3-11.

Question 10 Given two sorted arrays, denoted as array1 and array2, please merge them into array1 and keep the merged array sorted. Suppose there is sufficient vacant memory at the end of array1 to accommodate elements of array2.

All elements in an array are sequential, so some elements will be shifted when a new element is inserted. Supposing array1has m elements and array2 has n elements. Since O(m) elements will be shifted when an element of array2 is inserted toarray1, it costs O(mn) time to merge two arrays via insertions.

Inspired by the solution of the previous problem, it is better to copy and move elements from right to left. The last two elements of these two arrays are compared, and the greater one is copied to the location with index (m+n-1). It continues to compare and copy until no numbers in array2 are left. Sample code in C is shown in Listing 3-12.


import java.util.Arrays;

public class MergeTwoArrays {

    static int[] arr1=new int[]{1,3,4,5,7,7,9,11,13,15,17,19};
    static int[] arr2=new int[]{2,4,6,8,10,12,14,14,16,18,20,22};

    public static void main(String[] args){
        int FirstArrayLocation =0 ;
        int SecondArrayLocation=0;
        int[] mergeArr=new int[arr1.length + arr2.length];

        for ( int i=0; i<= arr1.length + arr2.length; i++){
            if (( FirstArrayLocation < arr1.length ) && (SecondArrayLocation < arr2.length)){
                if ( arr1[FirstArrayLocation] <= arr2[SecondArrayLocation]){
                    mergeArr[i]=arr1[FirstArrayLocation];
                    FirstArrayLocation++;
                }else{
                    mergeArr[i]=arr2[SecondArrayLocation];
                    SecondArrayLocation++;
                }
            }
            else if(SecondArrayLocation < arr2.length){
                    mergeArr[i]=arr2[SecondArrayLocation];
                    SecondArrayLocation++;
            }else if ( FirstArrayLocation < arr1.length ){
                    mergeArr[i]=arr1[FirstArrayLocation];
                    FirstArrayLocation++;
            }
        }
    }
}

Question 11 How do you implement a function to match regular expressions with ‘.’ and ‘*’ in patterns? The character ‘.’ in a pattern matches a single character, and ‘*’ matches zero or any number of characters preceding it. Matching means that a string fully matches the pattern where all characters in a string match the whole pattern. For example, the string “aaa” matches the pattern “a.a” and the pattern “ab*ac*a”. However, it does not match the pattern “aa.a” nor “ab*a”.

Our solution matches a character after another from a string and a pattern. Let’s first analyze how to match a character. When the character ch in the pattern is a ‘.’, it matches whatever character is in the string. If the character ch is not a ‘.’ and the character in the string is ch, they match each other. When the first characters in a string and a pattern are matched, we continue to match the remaining string and pattern.

It is easy to match when the second character in the remaining pattern is not a ‘*’. If the first character in the remaining string matches the first character in the remaining pattern, it advances the string and pattern and continues to match next characters; otherwise, it returns false directly.

images

Figure 3-5. The nondeterministic finite automaton for the pattern ba*ab. There are two choices when it enters the state 2 with an input ‘a’: it advances to the state 3 or returns back to the state 2.

It is more complex when the second character in the remaining pattern is a ‘*’ because there might be multiple matching choices. One choice is to advance the pattern by two characters because a ‘*’ may match zero characters in a string. In such a case, a ‘*’ and its preceding character are ignored. If the first character in the remaining string matches the character before the ‘*’ in the pattern, it may advance forward in the string and it has two choices in the pattern: it may advance the pattern by two characters or keep the pattern unchanged.

As shown in the nondeterministic finite automaton of Figure 3-5, it has two choices in the state 2 with an input ‘a’: it may advance to the state 3 (advance on the pattern by two characters) or return back to state 2 (keeping the pattern unchanged for the next round of matching).

The solution can be implemented based on recursion, as shown in

 

댓글 남기기