string - 反转字符串中单词中的字母

Question

我编写了以下解决方案，它可以工作，除非有标点符号。我想知道是否有 O(1) 空间复杂度和 O(字符串长度) 时间复杂度解决方案，而无需使用 reverse() 方法或任何类似的方法使此任务太容易。任何可以正确处理标点符号的答案都会很棒。

例子:

给定字符串:“我喜欢巧克力”

返回字符串应该是:“I evol etalocohc”

为清楚起见，当我说正确处理标点符号时，我的意思是标点符号不应四处移动。

 // reverse the letters of every word in a sentence (string), and return the result

 public static String reverse(String x)
 {
     String[] str = x.split(" ");

     StringBuilder rev = new StringBuilder("");

     for (int i = 0; i < str.length; i++)
     {
         for (int s = str[i].length()-1; s >= 0; s--)
         {
             rev.append(str[i].charAt(s));
         }
         rev.append(" ");
     }

     return rev.toString();
 }

这是我的一些测试的输出:

     public static void main(String[] args)
     {
         System.out.println(reverse("I love chocolate"));//this passes
         System.out.println(reverse("Geeks for Geeks"));//this passes
         System.out.println(reverse("You, are awesome"));//not handling puncutation mark correctly, gives me ",uoY era emosewa", instead of "uoY, era emosewa"
         System.out.println(reverse("Geeks! for Geeks."));//not handling puncutation marks correctly, gives me "!skeeG rof .skeeG", instead of "skeeG! rof skeeG."
     }

Answer 1

这可能适用于标点符号:

public static String reverse(String x)
{
     String[] str = x.split("\\W"); //Split on non-word characters.

     StringBuilder rev = new StringBuilder("");
     int currentPosition = 0;
     for (int i = 0; i < str.length; i++)
     {
         for (int s = str[i].length()-1; s >= 0; s--)
         {
             rev.append(str[i].charAt(s));
             currentPosition++;
         }
         while (currentPosition < x.length() && Character.toString(x.charAt(currentPosition)).matches("\\W")) 
            rev.append(x.charAt(currentPosition++)); //Add the actual character there.
     }

     return rev.toString();
 }

有一段时间没有用 Java 编码了，所以我知道这可能不是这里的最佳实践。

复杂度为 O(n)(空间和时间)。

如果您从字符串生成器开始，您可能可以通过使用就地字符交换而不是附加来降低空间复杂度，但您需要先发制人地找到所有非单词字符的位置。