编写一个方法，将字符串中的所有空格替换为'%20'

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):

问题状态:编写一个方法以“%20”替换字符串中的所有空格。假设字符串在字符串末尾有足够的空间来容纳额外的字符，并且给定一个字符串的真实长度。我使用了books代码，使用字符数组实现了Java中的解决方案(考虑到Java字符串是不可变的):

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?

我从replaceSpaces()调用中得到的输出是:%20do，它剪切原始数组的最后一个字符。我一直在思考这个问题，谁能解释一下为什么算法会这么做?

21 个解决方案

#1

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

你把长度除以6，这就造成了这个。传递长度为7，包括空间。其他明智的

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

通过这两个更改，我得到了输出:%20dog

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

1)将空格数改为2[因为长度已经包含%20所需的3个字符中的1个]

newLength = length + (spaceCount * 2);

2) Loop should start on length

2)循环应该从长度开始

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

这是我的问题代码。好像是为我工作。如果您有兴趣，请看一看。它是用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)

这是我的解决方案。我检查ascii码32，然后把它改为%20。这个解的时间复杂度是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()

在reald世界编程中，我建议:URLEncoder.encode()

#7

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

您还可以使用子字符串方法和空间的ascii(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

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 :)

这段代码工作:)

#9

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

这是正确的。然而，使用StringBuffer对象会增加空间复杂性。

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

#10

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

#11

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

另一种方法。我假设尾空间不需要转换为%20，尾空间为%20提供了足够的空间来填充中间

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

#12

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. 反转给定的字符串并检查第一个字符出现的位置。
3. Using string builder to append "02%" for spaces - since the string is reversed.
4. 使用字符串构建器为空格添加“02%”——因为字符串是反向的。
5. Finally reverse the string once again.
6. 最后，再次反转字符串。

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

注意:我们对字符串进行反向操作，以防止在末尾空格中添加“%20”。

Hope that helps!

希望会有帮助!

#13

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] = ' ';
        }

    }

}

#14

Any reason not to use 'replace' method?

有什么理由不使用“替换”方法吗?

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

#15

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

嗯……我也在想这个问题。想想我在这里看到的。book解决方案不适合Java，因为它使用了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.

这里使用char[]或return void的修改和解决方案并不适用，因为Java不使用指针。

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

这看起来很好，我想，你只需要一个通过字符串，所以复杂度应该是O(n)对吧?错了!问题是在

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

它实际上复制一个字符串并创建它的一个副本。在java字符串中表示为。

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 :)

这使得它们是不可变的(为了获取更多信息，我将检查java.lang。字符串及其工作方式)。这一事实将提高该算法的复杂性O(N ^ 2)和卑鄙的招聘人员可以利用这一点来失败:P因此,我用一个新的低层次的解决方案,您将永远不会使用在实践中,但在理论上可以:)

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

#16

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

#17

Question : Urlify the spaces with %20

问题:用%20对空格进行Urlify

Solution 1 :

解决方案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

#18

My solution using StringBuilder with time complexity O(n)

我的解决方案是使用具有时间复杂度O(n)的StringBuilder

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

#19

Can you use StringBuilder?

你能使用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();
}

#20

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

#21

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

我也在看书中的那个问题。我想我们可以用String。trim()和String。replaceAll(" "," % 20)