## Monday, April 17, 2017

### LeetCode 557 - Reverse Words in a String III

https://leetcode.com/problems/reverse-words-in-a-string-iii
Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
Example 1:
```Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"
```
Note: In the string, each word is separated by single space and there will not be any extra space in the string.
https://discuss.leetcode.com/topic/85911/easiest-java-solution-9ms-similar-to-reverse-words-in-a-string-ii
Step 1. Convert the string to char[] array
Step 2. Whenever I encounter a space ' ' , I call the reverse function ( just to keep the code clean )
Step 3. Repeat till the end!
``````public String reverseWords(String s)
{
char[] s1 = s.toCharArray();
int i = 0;
for(int j = 0; j < s1.length; j++)
{
if(s1[j] == ' ')
{
reverse(s1, i, j - 1);
i = j + 1;
}
}
reverse(s1, i, s1.length - 1);
return new String(s1);
}

public void reverse(char[] s, int l, int r)
{
while(l < r)
{
char temp = s[l];
s[l] = s[r];
s[r] = temp;
l++; r--;
}
}``````
Yes your solution will work. But I think my solution will be faster because you are checking (j == n) every time and performing i = j + 1 for the last call which is unnecessary.
my solution - Run time : 9ms (94.42 %)
yours - Run time : 10ms (88.72 %)
``````    public String reverseWords(String s) {
int n = s.length();
char[] c = s.toCharArray();
for (int i = 0, j = 1; j <= n; j++) {
if (j == n || c[j] == ' ') {
reverse(c, i, j-1);
i = j+1;
}
}
return new String(c);
}

private void reverse(char[] c, int i, int j) {
while (i < j) {
char temp = c[i];
c[i] = c[j];
c[j] = temp;
i++; j--;
}
}``````
https://discuss.leetcode.com/topic/85784/c-java-clean-code
``````    public String reverseWords(String s) {
char[] ca = s.toCharArray();
for (int i = 0; i < ca.length; i++) {
if (ca[i] != ' ') {   // when i is a non-space
int j = i;
while (j + 1 < ca.length && ca[j + 1] != ' ') { j++; } // move j to the end of the word
reverse(ca, i, j);
i = j;
}
}
return new String(ca);
}

private void reverse(char[] ca, int i, int j) {
for (; i < j; i++, j--) {
char tmp = ca[i];
ca[i] = ca[j];
ca[j] = tmp;
}
}``````

https://discuss.leetcode.com/topic/85744/java-solution
``````public String reverseWords(String s) {
String[] strs = s.split(" ");
StringBuffer sb = new StringBuffer();
for(String str: strs){
StringBuffer temp = new StringBuffer(str);
sb.append(temp.reverse());
sb.append(" ");
}
sb.setLength(sb.length()-1);
return sb.toString();
}``````

## Labels

LeetCode (1243) GeeksforGeeks (1129) Review (896) Algorithm (764) LeetCode - Review (722) to-do (636) Dynamic Programming (340) Classic Algorithm (313) Classic Interview (266) Google Interview (246) Tree (146) POJ (141) Difficult Algorithm (129) LeetCode - Phone (127) EPI (125) Bit Algorithms (120) Different Solutions (117) Math (115) Lintcode (113) Smart Algorithm (105) DFS (93) Binary Search (92) HackerRank (89) Greedy Algorithm (84) Binary Tree (83) Stack (78) Graph Algorithm (76) Two Pointers (64) BFS (63) Interview Corner (61) List (57) Interval (54) Codility (53) ComProGuide (52) LeetCode Hard (50) Trie (49) Union-Find (48) Segment Tree (47) USACO (46) Bisection (42) ACM-ICPC (41) Data Structure (40) Knapsack (40) Matrix (40) Time Complexity (40) Jobdu (39) Priority Queue (39) Sliding Window (39) Backtracking (38) String Algorithm (38) TopCoder (38) Codeforces (36) Must Known (36) Sort (35) prismoskills (33) Array (32) LeetCode - DP (32) HDU (31) Random (31) Google Code Jam (30) Graph (30) Permutation (30) Puzzles (30) Array O(N) (29) Company-Airbnb (29) Palindrome (29) Company-Zenefits (28) Pre-Sort (28) to-do-must (28) Logic Thinking (27) Monotonic Stack (27) Queue (27) Follow Up (25) GeeksQuiz (25) hihocoder (25) Company-Facebook (24) Algorithm Game (22) Hash (22) High Frequency (22) Merge Sort (22) DFS + Review (21) O(N) (21) Brain Teaser (20) CareerCup (20) BST (19) Hard (19) Topological Sort (19) UVA (19) Sweep Line (18) Company-Uber (17) Game Theory (17) Probabilities (17) Proof (17) Codercareer (16) DP - Tree (16) Heap (16) Iterator (16) Shortest Path (16) String Search (16) Tree Traversal (16) itint5 (16) Difficult (15) KMP (15) Reverse Thinking (15) LeetCode - DFS (14) Number (14) Number Theory (14) Rolling Hash (14) TreeMap (14) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Euclidean GCD (13) Majority (13) mitbbs (13) Combination (12) Modify Tree (12) Reconstruct Tree (12) Simulation (12) 尺取法 (12) AOJ (11) Bucket Sort (11) DFS+Backtracking (11) DP - Interval (11) Graph DFS (11) LCA (11) Math-Divisible (11) Miscs (11) O(1) Space (11) Prefix Sum (11) Princeton (11) X Sum (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Cache (10) DP - Bit Masking (10) DP - Digit (10) HackerRank Easy (10) Interval Tree (10) MinMax (10) SPOJ (10) Theory (10) Tutorialhorizon (10) Mathblog (9) Max-Min Flow (9) Quick Sort (9) Stock (9) Use XOR (9) Book Notes (8) Bottom-Up (8) DFS+BFS (8) Dijkstra (8) Linked List (8) Prime (8) Quick Select (8) Suffix Tree (8) Summary (8) Tech-Queries (8) TreeSet (8) 穷竭搜索 (8) Expression (7) Game Nim (7) Graph BFS (7) Hackerearth (7) Inversion (7) One Pass (7) Pruning (7) Radix Sort (7) Tree DP (7) 蓝桥杯 (7) Bit Mask (6) DFS+DP (6) Dutch Flag (6) Flood fill (6) How To (6) Manacher (6) Pre-Sum (6) Rabin-Karp (6) Sampling (6) Schedule (6) Stream (6) Suffix Array (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Big Data (5) Brute Force (5) Code Kata (5) Coding (5) Convex Hull (5) Crazyforcode (5) Cycle (5) Find Rule (5) Graph Cycle (5) Immutability (5) Java (5) Maze (5) Quadtrees (5) Quora (5) Subarray Sum (5) Sudoku (5) Threaded (5) Word Search (5) jiuzhang (5) 1point3acres (4) Abbreviation (4) Anagram (4) Anagrams (4) Chess Game (4) Dequeue (4) Distributed (4) Greedy (4) Histogram (4) MST (4) N Queens (4) Probability (4) Subset Sum (4) Subsets (4) Symbol Table (4) Triangle (4) Water Jug (4) algnotes (4) fgdsb (4) to-do-2 (4) 最大化最小值 (4) 树形DP (4) 男人八题 (4) A Star (3) B Tree (3) Bellman Ford (3) Coins (3) Dedup (3) Dropbox (3) Easy (3) Factor (3) Github (3) GoLang (3) Islands (3) Joseph (3) K (3) Knight (3) LogN (3) Median (3) Minesweeper (3) NP Hard (3) Parentheses (3) Parser (3) Programcreek (3) Rectangle (3) Robot (3) Scala (3) SegmentFault (3) Shuffle (3) Skyline (3) Subtree (3) TSP (3) Trie + DFS (3) Word Ladder (3) bookkeeping (3) codebytes (3) Array Merge (2) BOJ (2) Bit Counting (2) Bloom Filter (2) Cache (2) Clock (2) Codesays (2) DP - DFS (2) DP - Trie (2) DP-3D Table (2) DP-Classical (2) DP-i-k-j (2) Game (2) GoHired (2) Graham Scan (2) Huffman Tree (2) Invariant (2) Jump Game (2) Lucene-Solr (2) Matrix Power (2) O(N) Hard (2) Peak (2) PreProcess (2) Programming (2) Reverse (2) Rosettacode (2) Search (2) SimHash (2) Sparse Table (2) TV (2) Tile (2) Tree Sum (2) Two-End-BFS (2) Word Break (2) Word Graph (2) Word Trie (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) ? (1) Akka (1) BACK (1) BFS Hard (1) BK-Tree (1) BZOJ (1) Basic (1) Bayes (1) Big Integer (1) Big Number (1) Binary (1) Bipartite (1) BitMap (1) BitMap index (1) BitSet (1) BuildIt (1) C/C++ (1) CC Interview (1) Chinese (1) Circular (1) Clean Code (1) Cloest (1) Clone (1) Code Quality (1) Company-Epic (1) Company-Yelp (1) Concise (1) Concurrency (1) Custom Sort (1) DFS + RL (1) DFS-Matrix (1) DI (1) DP-Difficult (1) DP-Graph (1) DP-MaxMin (1) DP-树形 (1) Database (1) Diagonal (1) Domino (1) Dr Dobb's (1) Duplicate (1) EntryPoint (1) FST (1) Fraction (1) Funny (1) Generation (1) GeoHash (1) Google APAC (1) Gray Code (1) HOJ (1) Hanoi (1) How Hash (1) How to Test (1) Improve It (1) In Place (1) Interview (1) Isomorphic (1) JDK8 (1) Kruskal (1) Kth Element (1) Lazy (1) LeetCode -P (1) Linkedin (1) Local MinMax (1) Lock (1) Matrix BFS (1) Matrix Graph (1) Matrix+DP (1) MinHash (1) MinMax Heap (1) Monto Carlo (1) Multiple DFS (1) Next Element (1) O(32N) (1) Optimal Play (1) Optimization (1) PAT (1) Parenthesis (1) Partition (1) Path Finding (1) Persistent (1) Power Set (1) Python (1) RSA (1) Ranking (1) Rddles (1) ReHash (1) Realtime (1) Recursion (1) Region (1) Remap (1) Resources (1) Robin (1) Selection (1) Similarity (1) Simplify (1) Square (1) Strategy (1) String DP (1) SubMatrix (1) Subsequence (1) Test (1) Test Cases (1) Thread (1) TimSort (1) Top-Down (1) Tournament (1) Trade Off (1) Tree Rotate (1) Trie vs Hash (1) Triplet (1) Two Stacks (1) UyHiP (1) Valid Tree (1) Vector (1) Wiggle Sort (1) Wikipedia (1) ZOJ (1) ZigZag (1) codevs (1) cos126 (1) cycl (1) javabeat (1) jum (1) sqrt(N) (1) 两次dijkstra (1) 九度 (1) 二进制枚举 (1) 夹逼法 (1) 归一化 (1) 折半枚举 (1) 枚举 (1) 状态压缩DP (1) 英雄会 (1) 逆向思维 (1)