Showing posts with label reverse. Show all posts
Showing posts with label reverse. Show all posts

Sunday, August 7, 2016

186. Reverse Words in a String II

This is similar to problem "151. Reverse Words in a String". The idea is the same, i.e. reverse all the string first and reverse each word in the string.

1:  class Solution {  
2:  public:  
3:    void reverseWords(string &s) {  
4:      reverse(s.begin(), s.end());  
5:      int i = 0, j = 0;  
6:      while (i < s.size()) {  
7:        while (i < s.size() && s[i] != ' ') i++;  
8:        reverse(s.begin()+j, s.begin()+i);  
9:        j = ++i;  
10:      }  
11:    }  
12:  };  

Tuesday, July 5, 2016

151. Reverse Words in a String

The idea is to reverse the whole string first and reverse each word in the string. However, we need to preprocess the string first to get a "clean" one, i.e. no leading and trailing spaces and no extra spaces between two words.

1:  class Solution {  
2:  public:  
3:    void reverseWords(string &s) {  
4:      preprocess(s);  
5:      reverse(s.begin(), s.end());  
6:      int i = 0, j = 0;  
7:      for (; i < s.size(); i++) {  
8:        if (s[i] == ' ') {  
9:          reverseWord(s, j, i-1);  
10:          j = i+1;  
11:        }  
12:      }  
13:      if (j != s.size()) reverseWord(s, j, s.size()-1);  
14:    }  
15:    void reverseWord(string &s, int i, int j) {  
16:      while (i < j) {  
17:        swap(s[i++], s[j--]);  
18:      }  
19:    }  
20:    void preprocess(string &s) {  
21:      int i = 0, j = 0;  
22:      for (; i < s.size(); i++) if (s[i] != ' ') break;  
23:      if (i != 0) s.erase(s.begin(), s.begin()+i);  
24:      for (i = s.size()-1; i >= 0; i--) if (s[i] != ' ') break;  
25:      if (i != s.size()-1) s.erase(s.begin()+i+1, s.end());  
26:      for (i = 0, j = 0; i < s.size(); i++) {  
27:        if (s[i] == ' ') {  
28:          j = i+1;  
29:          while (s[j] == ' ') j++;  
30:          if (j != i+1) s.erase(s.begin()+i+1, s.begin()+j);  
31:        }  
32:      }  
33:    }  
34:  };  

When I revisited this problem, I combined reversing single word and eliminating redundant spaces into one loop. I made mistakes in
line 21: I only need to delete redundant spaces which means i-j>1
line 22: For next loop, j must point to the beginning letter of the word.

1:  class Solution {  
2:  public:  
3:    void reverseWords(string &s) {  
4:      if (s.empty()) return;  
5:      // trim leading spaces  
6:      int i = 0, j = 0;  
7:      while (i < s.size() && s[i] == ' ') i++;  
8:      s = s.substr(i);  
9:      // trim tailing spaces  
10:      i = s.size() - 1;  
11:      while (i >= 0 && s[i] == ' ') i--;  
12:      s = s.substr(0, i+1);  
13:      reverse(s.begin(), s.end());  
14:      i = 0, j = 0;  
15:      while (i < s.size()) {  
16:        while (i < s.size() && s[i] != ' ') i++;  
17:        reverse(s.begin()+j, s.begin()+i);  
18:        j = i;  
19:        while (i < s.size() && s[i] == ' ') i++;  
20:        if (i - j > 1) s.erase(s.begin()+j, s.begin()+i-1);  
21:        i = ++j;  
22:      }  
23:    }  
24:  };  

Sunday, June 26, 2016

92. Reverse Linked List II

This problem can be done in two parts.
(1) move pointer to position m.
(2) reverse sublist from m to n. Note, the first node in the sublist will be the tail in the reversed list so we just need to move the node behind it to the head of the sublist by insertion. Also note prev->next will always be the head of the sublist no matter it is done with the reverse.

I made several mistakes here.
(1) In line 23, I was trying to link p->next to cur. This is true for the first round but it is wrong since then because cur is moved forward by inserting a tail node before it. Instead, we are inserting tail node before head which is actually prev->next.
(2) I was trying to move prev to next. Note, prev is always fixed here as in the sublist, we try to insert tail node before head which is right after prev.
(3) I was trying to compute n after line 17. Note after line 17, m has become 0.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* reverseBetween(ListNode* head, int m, int n) {  
12:      if (m == n) return head;  
13:      n -= m;  
14:      ListNode *dummy = new ListNode(-1);  
15:      dummy->next = head;  
16:      ListNode *prev = dummy;  
17:      while (--m) prev = prev->next;  
18:      ListNode *cur = prev->next;  
19:      // we don't need to move prev.  
20:      while (n--) {  
21:        ListNode *p = cur->next;  
22:        cur->next = p->next;  
23:        p->next = prev->next;  
24:        prev->next = p;  
25:      }  
26:      return dummy->next;  
27:    }  
28:  };