Write a method to replace all spaces in a string w

问题:

I have a question about a programming problem from the book Cracking The Code Interview by Gayl Laakmann McDowell, 5th Edition.

The problem states: Write a method to replace all spaces in a string with '%20'. Assume string has sufficient space at end of string to hold additional characters, and that you're given a true length of a string. I used the books code, implementing the solution in Java using a character array (given the fact that Java Strings are immutable):

public class Test {
    public void replaceSpaces(char[] str, int length) {
        int spaceCount = 0, newLength = 0, i = 0;

        for(i = 0; i < length; i++) {
            if (str[i] == ' ') 
                spaceCount++;
        }

        newLength = length + (spaceCount * 2);
        str[newLength] = '\0';
        for(i = length - 1; i >= 0; i--) {
            if (str[i] == ' ') {
                str[newLength - 1] = '0';
                str[newLength - 2] = '2';
                str[newLength - 3] = '%';
                newLength = newLength - 3;
            }
            else {
                str[newLength - 1] = str[i];
                newLength = newLength - 1;
            }
        }
        System.out.println(str);
    }

    public static void main(String[] args) {
        Test tst = new Test();
        char[] ch = {'t', 'h', 'e', ' ', 'd', 'o', 'g', ' ', ' ', ' ', ' ', ' ', ' '};
        int length = 6;
        tst.replaceSpaces(ch, length);  
    }
}

The output I am getting from the replaceSpaces() call is: the%20do which is cutting of the last character of the original array. I have been scratching my head over this, can anyone explain to me why the algorithm is doing this?

回答1:

You are passing the length as 6, which is causing this. Pass length as 7 including space. Other wise

for(i = length - 1; i >= 0; i--) {

will not consider last char.

回答2:

public String replace(String str) {
    String[] words = str.split(" ");
    StringBuilder sentence = new StringBuilder(words[0]);

    for (int i = 1; i < words.length; ++i) {
        sentence.append("%20");
        sentence.append(words[i]);
    }

    return sentence.toString();
}

回答3:

With these two changes I got the output: the%20dog

1) Change space count to 2 [since length already includes 1 of the 3 characters you need for %20]

newLength = length + (spaceCount * 2);

2) Loop should start on length

for(i = length; i >= 0; i--) {

回答4:

This is my code for this question. Seems like working for me. If you're interested, please have a look. It's written in JAVA

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));
  }
}

回答5:

Here is my solution. I check for the ascii code 32 then put a %20 instead of it.Time complexity of this solution is O(N)

public String replace(String s) {

        char arr[] = s.toCharArray();
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 32)
                sb.append("%20");
            else
                sb.append(arr[i]);

        }

        return sb.toString();
    }

回答6:

Is it about jab interview-questions?

In reald world programming I would suggest: URLEncoder.encode()

回答7:

You can also use substring method and the ascii for space (32).

public String replaceSpaceInString(String s){
    int i;
    for (i=0;i<s.length();i++){
        System.out.println("i is "+i);
        if (s.charAt(i)==(int)32){
            s=s.substring(0, i)+"%20"+s.substring(i+1, s.length());
            i=i+2;              
            }
    }
    return s;
    }

To test:

System.out.println(cc.replaceSpaceInString("mon day "));

Output:

mon%20day%20

回答8:

You could just do this. No need to calculate the length or whatever. Strings are immutable anyways.

import java.util.*;
public class ReplaceString {

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        String str=in.nextLine();
        String n="";
        for(int i=0;i<str.length();i++)
        {
            if(str.charAt(i)==' ')
                n=n+"%20";
            else
                n=n+str.charAt(i);
        }
        str=n;
        System.out.println(str);
    }
}

回答9:

void Rep_Str(char *str)
{
    int j=0,count=0;
    int stlen = strlen(str);
    for (j = 0; j < stlen; j++)
    {
        if (str[j]==' ')
        {
            count++;
        }
    }

    int newlength = stlen+(count*2);
    str[newlength--]='\0';
    for (j = stlen-1; j >=0 ; j--)
    {
        if (str[j]==' ')
        {
            str[newlength--]='0';
            str[newlength--]='2';
            str[newlength--]='%';
        }

        else
        {

            str[newlength--]=str[j];
        }
    }
}

This code works :)

回答10:

We can use a regular expression to solve this problem. For example:

public String replaceStringWithSpace(String str){
     return str.replaceAll("[\\s]", "%20");
 }

回答11:

This works correctly. However, using a StringBuffer object increases space complexity.

    Scanner scn = new Scanner(System.in);
    String str = scn.nextLine();
    StringBuffer sb = new StringBuffer(str.trim());

    for(int i = 0;i<sb.length();i++){
        if(32 == (int)sb.charAt(i)){
            sb.replace(i,i+1, "%20");
        }
    }

回答12:

public static String replaceAllSpaces(String s) {
    char[] c = s.toCharArray();
    int spaceCount = 0;
    int trueLen = s.length();
    int index = 0;
    for (int i = 0; i < trueLen; i++) {
        if (c[i] == ' ') {
            spaceCount++;
        }
    }
    index = trueLen + spaceCount * 2;
    char[] n = new char[index]; 
    for (int i = trueLen - 1; i >= 0; i--) {
        if (c[i] == ' ') {
            n[index - 1] = '0';
            n[index - 2] = '2';
            n[index - 3] = '%';
            index = index - 3;
        } else {
            n[index - 1] = c[i];
            index--;
        }
    }
    String x = new String(n);
    return x;
}

回答13:

Another way of doing this. I am assuming the trailing spaces don't need to be converted to %20 and that the trailing spaces provide enough room for %20s to be stuffed in between

public class Main {

   public static void main(String[] args) {

      String str = "a sd fghj    ";
      System.out.println(replacement(str));//a%20sd%20fghj
   }

   private static String replacement(String str) {
      char[] chars = str.toCharArray();
      int posOfLastChar = 0;
      for (int i = 0; i < chars.length; i++) {
         if (chars[i] != ' ') {
            posOfLastChar = i;
         }
      }

      int newCharPosition = chars.length - 1;

      //Start moving the characters to th end of the array. Replace spaces by %20
      for (int i = posOfLastChar; i >= 0; i--) {

         if (chars[i] == ' ') {
            chars[newCharPosition] = '0';
            chars[--newCharPosition] = '2';
            chars[--newCharPosition] = '%';
         } else {
            chars[newCharPosition] = chars[i];
         }

         newCharPosition--;
      }

      return String.valueOf(chars);
   }
}

回答14:

public class ReplaceChar{

 public static void main(String []args){
   String s = "ab c de  ";
   System.out.println(replaceChar(s));

 }

 public static String replaceChar(String s){

    boolean found = false;
    StringBuilder res = new StringBuilder(50);
    String str = rev(s);
    for(int i = 0; i <str.length(); i++){

        if (str.charAt(i) != ' ')  { found = true; }
        if (str.charAt(i) == ' '&& found == true) { res.append("%02"); }            
        else{ res.append(str.charAt(i)); }
    }
        return rev(res.toString()); 
 }

 // Function to reverse a string
 public static String rev(String s){
     StringBuilder result = new StringBuilder(50);
     for(int i = s.length()-1; i>=0; i-- ){
        result.append(s.charAt(i));
    }
    return result.toString();
 }}

A simple approach:

1. Reverse the given string and check where the first character appears.
2. Using string builder to append "02%" for spaces - since the string is reversed.
3. Finally reverse the string once again.

Note: We reverse the string so as to prevent an addition of "%20" to the trailing spaces.

Hope that helps!

回答15:

The question in the book mentions that the replacement should be in place so it is not possible to assign extra arrays, it should use constant space. You should also take into account many edge cases, this is my solution:

public class ReplaceSpaces {

    public static void main(String[] args) {
        if ( args.length == 0 ) {
            throw new IllegalArgumentException("No string");
        }
        String s = args[0];
        char[] characters = s.toCharArray();

        replaceSpaces(characters);
        System.out.println(characters);
    }

    static void replaceSpaces(char[] s) {
        int i = s.length-1;
        //Skipping all spaces in the end until setting `i` to non-space character
        while( i >= 0 && s[i] == ' ' ) { i--; }

        /* Used later to check there is enough extra space in the end */
        int extraSpaceLength = s.length - i - 1;

        /* 
        Used when moving the words right, 
        instead of finding the first non-space character again
        */
        int lastNonSpaceCharacter = i;

        /*
        Hold the number of spaces in the actual string boundaries
        */
        int numSpaces = 0;

        /*
        Counting num spaces beside the extra spaces
        */
        while( i >= 0 ) { 
            if ( s[i] == ' ' ) { numSpaces++; }
            i--;
        }

        if ( numSpaces == 0 ) {
            return;
        }

        /*
        Throw exception if there is not enough space
        */
        if ( extraSpaceLength < numSpaces*2 ) {
            throw new IllegalArgumentException("Not enough extra space");
        }

        /*
        Now we need to move each word right in order to have space for the 
        ascii representation
        */
        int wordEnd = lastNonSpaceCharacter;
        int wordsCounter = 0;

        int j = wordEnd - 1;
        while( j >= 0 ) {
            if ( s[j] == ' ' ){
                moveWordRight(s, j+1, wordEnd, (numSpaces-wordsCounter)*2);         
                wordsCounter++;
                wordEnd = j;
            }
            j--;
        }

        replaceSpacesWithAscii(s, lastNonSpaceCharacter + numSpaces * 2);

    }

    /*
    Replaces each 3 sequential spaces with %20
    char[] s - original character array
    int maxIndex - used to tell the method what is the last index it should
    try to replace, after that is is all extra spaces not required
    */
    static void replaceSpacesWithAscii(char[] s, int maxIndex) {
        int i = 0;

        while ( i <= maxIndex ) {
            if ( s[i] ==  ' ' ) {
                s[i] = '%';
                s[i+1] = '2';
                s[i+2] = '0';
                i+=2;
            } 
            i++;
        }
    }

    /*
    Move each word in the characters array by x moves
    char[] s - original character array
    int startIndex - word first character index
    int endIndex - word last character index
    int moves - number of moves to the right
    */
    static void moveWordRight(char[] s, int startIndex, int endIndex, int moves) {

        for(int i=endIndex; i>=startIndex; i--) {
            s[i+moves] = s[i];
            s[i] = ' ';
        }

    }

}

回答16:

Any reason not to use 'replace' method?

 public String replaceSpaces(String s){
    return s.replace(" ", "%20");}

回答17:

Hm... I am wondering about this problem as well. Considering what I have seen in here. The book solution does not fit Java because it uses in-place

 char []

modification and solutions in here that use char [] or return void don't fit as well because Java does not use pointers.

So I was thinking, the obvious solution would be

private static String encodeSpace(String string) {
     return string.replcaceAll(" ", "%20");
} 

but this is probably not what your interviewer would like to see :)

// make a function that actually does something
private static String encodeSpace(String string) {
     //create a new String
     String result = new String();
     // replacement
     final String encodeSpace = "%20";

     for(char c : string.toCharArray()) {
         if(c == ' ') result+=encodeString;
         else result+=c;
     }

     return result;
}

this looks fine I thought, and you only need one pass through the string, so the complexity should be O(n), right? Wrong! The problem is in

result += c;

which is the same as

result = result + c;

which actually copies a string and creates a copy of it. In java strings are represented as

private final char value[];

which makes them immutable (for more info I would check java.lang.String and how it works). This fact will bump up the complexity of this algorithm to O(N^2) and a sneaky recruiter can use this fact to fail you :P Thus, I came in with a new low-level solution which you will never use in practice, but which is good in theory :)

private static String encodeSpace(String string) {

    final char [] original = string != null? string.toCharArray() : new char[0];
    // ASCII encoding
    final char mod = 37, two = 50, zero = 48, space = 32;
    int spaces = 0, index = 0;

    // count spaces 
    for(char c : original) if(c == space) ++spaces; 

    // if no spaces - we are done
    if(spaces == 0) return string;

    // make a new char array (each space now takes +2 spots)
    char [] result = new char[string.length()+(2*spaces)];

    for(char c : original) {
        if(c == space) {
            result[index] = mod;
            result[++index] = two;
            result[++index] = zero;
        }
        else result[index] = c;
        ++index;
    }

    return new String(result);
}

回答18:

But I wonder what is wrong with following code:

private static String urlify(String originalString) {

        String newString = "";
        if (originalString.contains(" ")) {
            newString = originalString.replace(" ", "%20");
        }
        return newString;
    }

回答19:

Question : Urlify the spaces with %20

Solution 1 :

public class Solution9 {
public static void main(String[] args) {
    String a = "Gini Gina Protijayi";


       System.out.println(   urlencode(a));
}//main

public static String urlencode(String str) {
      str = str.trim();
        System.out.println("trim =>" + str);

        if (!str.contains(" ")) {
            return str;
        }

    char[] ca = str.toCharArray();

    int spaces = 0;
    for (char c : ca) {
        if (c == ' ') {
            spaces++;
        }
    }

    char[] newca = new char[ca.length + 2 * spaces];
      //  a pointer x has been added
    for (int i = 0, x = 0; i < ca.length; i++) {
        char c = ca[i];
        if (c == ' ') {
            newca[x] = '%';
            newca[x + 1] = '2';
            newca[x + 2] = '0';
            x += 3;
        } else {
            newca[x] = c;
            x++;
        }
    }
    return new String(newca);
}

}//urlify

回答20:

My solution using StringBuilder with time complexity O(n)

public static String url(String string, int length) {
    char[] arrays = string.toCharArray();
    StringBuilder builder = new StringBuilder(length);

    for (int i = 0; i < length; i++) {
        if (arrays[i] == ' ') {
            builder.append("%20");
        } else {
            builder.append(arrays[i]);
        }
    }

    return builder.toString();
}

Test case :

@Test
public void testUrl() {
    assertEquals("Mr%20John%20Smith", URLify.url("Mr John Smith ", 13));
}

回答21:

Can you use StringBuilder?

public String replaceSpace(String s)
{
    StringBuilder answer = new StringBuilder();
    for(int i = 0; i<s.length(); i++)   
    {
        if(s.CharAt(i) == ' ')
        {
            answer.append("%20");
        }
        else
        {
            answer.append(s.CharAt(i));
        }
    }
    return answer.toString();
}

回答22:

I am also looking at that question in the book. I believe we can just use String.trim() and String.replaceAll(" ", "%20) here

回答23:

I updated the solution here. http://rextester.com/CWAPCV11970

If we are creating new array and not in-place trasition, then why do we need to walk backwards?

I modified the real solution slightly to walk forward to create target Url-encoded-string.

Time complexity:

  O(n) - Walking original string
  O(1) - Creating target string incrementally

  where 'n' is number of chars in original string

Space complexity: O(n + m) - Duplicate space to store escaped spaces and string. where 'n' is number of chars in original string and 'm' is length of escaped spaces

    public static string ReplaceAll(string originalString, char findWhat, string replaceWith)
    {
        var newString = string.Empty;
        foreach(var character in originalString)
            newString += findWhat == character? replaceWith : character + string.Empty;
        return newString;
    }

回答24:

class Program
{
    static void Main(string[] args)
    {
        string name = "Stack Over Flow ";
        StringBuilder stringBuilder = new StringBuilder();

        char[] array = name.ToCharArray(); ;

        for(int i = 0; i < name.Length; i++)
        {
            if (array[i] == ' ')
            {
                stringBuilder.Append("%20");
            }
            else
                stringBuilder.Append(array[i]);
        }



        Console.WriteLine(stringBuilder);
        Console.ReadLine();

    }
}

回答25:

public class Sol {

public static void main(String[] args) {
    String[] str = "Write a method to replace all spaces in a string with".split(" ");
    StringBuffer sb = new StringBuffer();
    int count = 0;

    for(String s : str){
        sb.append(s);
        if(str.length-1 != count)
        sb.append("%20");
        ++count;
    }

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

}

回答26:

public class Test {
    public static void replace(String str) {
        String[] words = str.split(" ");
        StringBuilder sentence = new StringBuilder(words[0]);

        for (int i = 1; i < words.length; i++) {
            sentence.append("%20");
            sentence.append(words[i]);
        }
        sentence.append("%20");
        System.out.println(sentence.toString());
    }
    public static void main(String[] args) {
        replace("Hello   World "); **<- Hello<3spaces>World<1space>**
    }
}

O/P:: Hello%20%20%20World%20

回答27:

`// Maximum length of string after modifications.

const int MAX = 1000;

// Replaces spaces with %20 in-place and returns
// new length of modified string. It returns -1

// if modified string cannot be stored in str[]

int replaceSpaces(char str[])

{
    // count spaces and find current length
    int space_count = 0, i;
    for (i = 0; str[i]; i++)
        if (str[i] == ' ')
            space_count++;

    // Remove trailing spaces
    while (str[i-1] == ' ')
    {
       space_count--;
       i--;
    }

    // Find new length.
    int new_length = i + space_count * 2 + 1;

    // New length must be smaller than length
    // of string provided.
    if (new_length > MAX)
        return -1;

    // Start filling character from end
    int index = new_length - 1;

    // Fill string termination.
    str[index--] = '\0';

    // Fill rest of the string from end
    for (int j=i-1; j>=0; j--)
    {
        // inserts %20 in place of space
        if (str[j] == ' ')
        {
            str[index] = '0';
            str[index - 1] = '2';
            str[index - 2] = '%';
            index = index - 3;
        }
        else
        {
            str[index] = str[j];
            index--;
        }
    }

    return new_length;
}

// Driver code
int main()
{
    char str[MAX] = "Mr John Smith   ";

    // Prints the replaced string
    int new_length = replaceSpaces(str);
    for (int i=0; i<new_length; i++)
        printf("%c", str[i]);
    return 0;
}`