反转句子中每个单词的字符。例如:
My name is alex
更改为
yM eman si xela
我想到了普通的 O(n) 时间算法，即使用两个指针指向单词的任一端并将其反转。
但是在下面的站点
(引用问题2的答案) 它给出了将其转换为链表并重复应用单个单词的链表反转更好。我在 Hackerearth 上找到了相同程序的以下解决方案:
http://learn.hackerearth.com/question/317/reverse-characters-of-each-word-in-a-sentence/
此解决方案需要 O(n) 时间和 O(n) 空间。我建议的解决方案占用 O(n) 时间 O(1) 空间。第二个如何更好？
以下是来自Hackerearth的代码:
public node stringReverseChars(node ll){
if(ll == null || ll.next == null)
return ll;
node tmp = ll;
node head = null, prev = null;
while(tmp != null){
while(tmp != null && tmp.data == ' '){
if(head == null)
head = tmp;
prev = tmp;
tmp = tmp.next;
}
if(tmp == null)
break;
node curr = tmp;
while(tmp.next != null && tmp.next.data != ' '){
tmp = tmp.next;
}
node np = tmp.next;
tmp.next = null;
node rev = reverseLL(curr);
if(prev != null)
prev.next = rev;
prev = curr;
curr.next = np;
if(head == null)
head = rev;
tmp = np;
}
return head;
}
最佳答案
我很怀疑其他方法是否更好。它们的内存使用率更差(Θ(n) 与 O(1) 相比)和引用的局部性更差(它们使用链表而不是数组)。我认为您的解决方案没有任何问题；事实上，我认为这是执行此操作的标准方法。
希望这对您有所帮助!
关于string - 句子中每个单词的反转字符，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23803344/