@LHearen Yeah, totally agree with you. If the string is not so long, I think that the breif solution is better.
Scar
@Scar
Posts made by Scar

RE: 5 lines C++ using <stringstream>

RE: 5 lines C++ using <stringstream>
Really short solution! However the following line:
s = temp + " " + s;
It will keep moving chars backwards every time you insert a new word, which might be close toO(n^2).
What about a longer solution:void reverseWords(string &s) { istringstream in(s); string word; s = ""; while (in >> word) { reverse(word.begin(), word.end()); s += word + " "; } if (!s.empty()) { s.pop_back(); reverse(s.begin(), s.end()); } }

DFS with offbyone problem
I just tried to solve this question with both BFS and DFS, and BFS worked while DFS failed.
It's weird that, if I submitted this solution, I would get runtime error, however, if I copied the test case to costum testcase, it worked fine.
I thought that my logic should be right, the process was similar to the BFS solution. Then I tried to compare the DFS one with my accepted solutoin, which was submitted several months ago, I found there was just an offbyone problem. Here is my DFS solution with runtime error:
class Solution { private: // change x< 0 and y < 0 to x < 1, y < 1 bool check(vector<vector<char>>& board, int x, int y, int m, int n) { return !(x < 0  y < 0  x >= m  y >= n  board[x][y] != 'O'); } void dfs(vector<vector<char>>& board, int x, int y, int m, int n, vector<vector<int>>& dir) { for (int i = 0; i < 4; i++) { int nx = x + dir[i][0], ny = y + dir[i][1]; if (check(board, nx, ny, m, n)) { board[nx][ny] = '#'; dfs(board, nx, ny, m, n, dir); } } } public: void solve(vector<vector<char>>& board) { if (board.size() == 0  board[0].size() == 0) return; int m = board.size(), n = board[0].size(); vector<vector<int>> dir = {{1, 0}, {1, 0}, {0, 1}, {0, 1}}; // Add all outside 'O' to our queue queue<pair<int, int>> q; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // Just need one of the bound if (board[i][j] == 'O' && !(i != 0 && j != 0 && i != m  1 && j != n  1)) { board[i][j] = '#'; dfs(board, i, j, m, n, dir); } } } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (board[i][j] == '#') board[i][j] = 'O'; else if (board[i][j] == 'O') board[i][j] = 'X'; } } } };
After I changed
x < 0  y < 0
to be
x < 1  y < 1
in the boundary checking function, it was accepted. I understand that, since we will call the dfs from the boundary of the matrix, we no longer need to check it again, but how to explain the runtime error if I just want to check it again? Anyone have any idea?

RE: My concise C++ solution with O(n) time and O(1) space, beating 100% solutions
Concise solution! Just two issues:

intervals.erase(intervals.begin() + i);
the deletion of an element in an array will lead to movements of all following elements, which means that we may need to move O(n^2) times in the worst case. E.g.,[1,2],[3,5],[6,7],[8,10],[12,16]
and[0, 17]
. In this case, we need to erase every interval in the original vector with a lot of movements. 
I have submitted the same solution for this problem for twice, it became much faster. It seems that the servers of leetcode become much faster?


RE: 52ms, C++, O(1) space, O(n) time, Commented code
It failed with the case: [10,7,4,8,6,40,23]. It's a bad sequence, but it returned true with your code. This might be a new test case.

RE: C++ 8ms vs 16ms dfs solution using pair<int,int> directions. Why such a difernce?
I think that there might be several reasons:
 Every time you do a recursive call, you need to create a new "dirs" in first method..
 You need to access vector "dirs" to update "nexti" and "nextj" in first mehtod, it's not slow but maybe still slower than using constant immediately.
 You will update both i and j in first method, while you just need to update one of them in the second dfs.
 You have 4 boundary check (worst case) in first dfs, while you just need one in the second dfs.