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

Question

我有一个关于编程问题的问题，来自 Gayl Laakmann McDowell 的《破解代码访谈》，第 5 版。

问题说明：编写一个方法，用 '%20' 替换字符串中的所有空格。假设字符串在字符串末尾有足够的空间来容纳额外的字符，并且你得到了一个字符串的真实长度。我使用了书籍代码，使用字符数组在 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);  
    }
}

我从replaceSpaces()调用中得到的输出是：%20do，它正在切割原始数组的最后一个字符。我一直在为此挠头，谁能向我解释为什么算法会这样做？

Answer 1

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

Answer 2

您将长度传递为 6，这导致了这种情况。传递长度为 7，包括空格。否则

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

不会考虑最后一个字符。

Answer 3

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

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

newLength = length + (spaceCount * 2);

2）循环应该从长度开始

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

Answer 4

这是我的解决方案。我检查 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();
    }

Answer 5

这是我的这个问题的代码。似乎为我工作。如果你有兴趣，请看看。它是用 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));
  }
}

Answer 6

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

此代码有效:)

Answer 7

你可以这样做。无需计算长度或其他任何东西。无论如何，字符串是不可变的。

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

Answer 8

您还可以使用 substring 方法和 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;
    }

去测试：

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

输出：

mon%20day%20

Answer 9

我们可以使用正则表达式来解决这个问题。例如：

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

Answer 10

请记住，当后者不是前导或尾随空格时，您只想将 ' ' 替换为 '%20'。上面的几个答案都没有说明这一点。对于它的价值，当我运行 Laakmann 的解决方案示例时，我得到“索引超出范围错误”。

这是我自己的解决方案，它运行 O(n) 并在 C# 中实现：

        public static string URLreplace(string str, int n)
        {
            var len = str.Length;

            if (len == n)
                return str;

            var sb = new StringBuilder();
            var i = 0;

            while (i < len)
            {
                char c = str[i];

                if (c == ' ')
                {
                    while (i < len && str[i] == ' ')
                    {
                        i++; //skip ahead
                    }
                }
                else
                {
                    if (sb.Length > 0 && str[i - 1] == ' ')
                        sb.Append("%20" + c);
                    else
                        sb.Append(c);
                    i++;
                }
            }

            return sb.ToString();
        }

测试：

        //Arrange
        private string _str = "                Mr  John  Smith   ";
        private string _result = "Mr%20John%20Smith";
        private int _int = 13;

        [TestMethod]
        public void URLified()
        {
            //Act
            var cleaned = URLify.URLreplace(_str, _int);

            //Assert
            Assert.IsTrue(cleaned == _result);
        }

Answer 11

公开课溶胶{

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

}

Answer 12

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

    }
}

Answer 13

这可以正常工作。但是，使用 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");
        }
    }

Answer 14

问题：用 %20 Urlify 空格

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

Answer 15

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

一个简单的方法：

1. 反转给定的字符串并检查第一个字符出现的位置。
2. 使用字符串生成器为空格附加“02%” - 因为字符串是相反的。
3. 最后再次反转字符串。

注意：我们反转字符串以防止在尾随空格中添加“%20”。

希望有帮助！

Answer 16

我也在看书中的这个问题。我相信我们可以在这里String.trim()使用String.replaceAll(" ", "%20)

Answer 17

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

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

Answer 18

嗯...我也想知道这个问题。考虑到我在这里看到的。本书解决方案不适合 Java，因为它使用就地

 char []

此处使用 char [] 或 return void 的修改和解决方案也不适合，因为 Java 不使用指针。

所以我在想，显而易见的解决方案是

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

但这可能不是你的面试官希望看到的:)

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

我认为这看起来不错，而且您只需要通过字符串一次，所以复杂度应该是 O(n)，对吧？错误的！问题出在

result += c;

这与

result = result + c;

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

private final char value[];

这使它们不可变（有关更多信息，我将检查java.lang.String及其工作原理）。这个事实会将这个算法的复杂性提高到 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);
}

Answer 19

我在这里更新了解决方案。http://rextester.com/CWAPCV11970

如果我们正在创建新数组而不是就地转换，那么为什么我们需要倒退呢？

我稍微修改了真正的解决方案以向前创建目标 Url-encoded-string。

时间复杂度：

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

  where 'n' is number of chars in original string

空间复杂度： O(n + m) - 用于存储转义空格和字符串的重复空间。其中'n'是原始字符串中的字符数，'m'是转义空格的长度

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

Answer 20

// 在传递输入时确保使用 .toCharArray 方法，因为字符串是不可变的

public static 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 = "Mr John Smith    ".toCharArray();
    int length = 13;
    replaceSpaces(ch, length);
}

Answer 21

我使用时间复杂度 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
public void testUrl() {
    assertEquals("Mr%20John%20Smith", URLify.url("Mr John Smith ", 13));
}

Answer 22

但我想知道以下代码有什么问题：

private static String urlify(String originalString) {

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

Answer 23

一行代码 System.out.println(s.trim().replace(" ","%20"));

Answer 24

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:: 你好%20%20%20World%20

Answer 25

书中的问题提到替换应该到位，因此不可能分配额外的数组，它应该使用常量空间。您还应该考虑许多边缘情况，这是我的解决方案：

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

    }

}

Answer 26

这样做的另一种方法。我假设尾随空格不需要转换为 %20 并且尾随空格为 %20s 之间填充提供了足够的空间

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

Answer 27

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

Answer 28

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

Answer 29

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