It's quite easy to solve it using recursion but the result is "Time Limit Exceeded" on some very long input.
I can convert the recursion to a for loop, but it's quite tedious and I feel I'm missing the whole point of the question.
Is there some kind of a trick here?
Is there a trick here or are we supposed to convert a recursion to a for loop?

Following is my solution that can AC, actually it is a dynamic programming code:
class Solution { public: bool isInterleave(string s1, string s2, string s3) { int len1 = s1.length(), len2 = s2.length(), len3 = s3.length(); if(len3 != len1 + len2)return false; bool res[len1 + 1][len2 + 1]; res[0][0] = true; for(int i = 1; i <= len2; i++)res[0][i] = s2.substr(0, i) == s3.substr(0, i); for(int i = 1; i <= len1; i++)res[i][0] = s1.substr(0, i) == s3.substr(0, i); for(int i = 1; i <= len1; i++) for(int j = 1; j <= len2; j++){ res[i][j] = (s3[i + j  1] == s1[i  1] && res[i  1][j])  (s3[i + j  1] == s2[j  1] && res[i][j  1]); } return res[len1][len2]; } };
res[i][j] indicates whether s3.substr(0, i + j) is the interleaving string of s1.substr(0, i) and s2.substr(0, j). The transmitting function is res[i][j] = (s3[i + j  1] == s1[i  1] && res[i  1][j]) 
(s3[i + j  1] == s2[j  1] && res[i][j  1]); So, res[len1][len2] is the finally result.

Recursion or forloop is not the keypoint. I also wrote a forloop and it still report that time exceeds. here is my code:
class Solution { public: bool isInterleave(string s1, string s2, string s3) { int i1 = 0, i2 = 0, i3 = 0; if (s1.length() + s2.length() != s3.length() ) { return false; } else { if (s1 == s3) return true; if (s2 == s3) return true; } return isInterleave(s1, i1, s2, i2, s3, i3); } bool isInterleave(string s1, int i1, string s2, int i2, string s3, int i3) { stack<int> s; bool ret = true; while(i1 + i2 < s3.length()) { if (s1[i1] == s3[i3] && s2[i2] != s3[i3]) { i1++; i3++; } else if (s1[i1] != s3[i3] && s2[i2] == s3[i3]) { i2++; i3++; } else if (s1[i1] == s3[i3] && s2[i2] == s3[i3]) { s.push(i1); s.push(i2); s.push(i3); i1++; i3++; } else if (!s.empty()) { i3 = s.top(); s.pop(); i2 = s.top(); s.pop(); i1 = s.top(); s.pop(); /* take the untaken path */ i2++; i3++; } else { ret = false; break; } } return ret; } };

Thank you for the hint.
I read this interesting page:
http://en.wikipedia.org/wiki/Dynamic_programming#Dynamic_programming_in_computer_programming
Then I implemented it and worked out.
I just used stl containers to cache results.
Passed.

My DP solution with O(S1 * S2) time complex and O(max(S1, S2)) space complex, AC in 16ms:
bool isInterleave(string s1, string s2, string s3) { if (s1.size() + s2.size() != s3.size()) return false; if (s1.size() < s2.size()) s1.swap(s2); vector<bool> dp(s1.size() + 1); for (size_t j = 0; j <= s2.size(); ++j){ dp[0] = (!j  (dp[0] && s2[j  1] == s3[j  1])); for (size_t i = 1; i <= s1.size(); ++i) dp[i] = ((dp[i  1] && s1[i  1] == s3[i + j  1])  (j > 0 && dp[i] && s2[j  1] == s3[i + j  1])); } return dp.back(); }

Ok, you catch me!
I reviewed my solution and found a mistake, which generate wrong answer when s1="a", s2=“b" and s3="aa". So I modified it, now it should be right.
Talking about the swap of s1 and s2, I just want to make fewer iterations for the outer loop, which I think may improve the code locality.
Thank you for the eagle eyes!

Hi, firstly I have figured out the recursion solution just like you, and obviously get TLE. Then I realize the recursive solution solve sub problems again and again, which indicates DP is a better solution. But I don't want give up my recursion code (and too lazy to work out a DP solution).
So, based on the original code I added a Map to cache the result of every sub problem. When to solve a problem, we first lookup the Map; once we get result, we put it into the Map. This cache way works like a charm. After all, the key of DP is to cache intermediate results, which the Map in my case does the same job.

Recursive Solution with cache can AC
public class Solution { public boolean isInterleave(String s1, String s2, String s3) { if(s1 == null  s2 == null  s3 == null  s1.length() + s2.length() != s3.length()){ return false; } Map<String, Boolean> cache = new HashMap<>(); return isInterleave(s1.toCharArray(), 0, s2.toCharArray(), 0, s3.toCharArray(), cache); } boolean isInterleave(char[] a1, int i, char[] a2, int j, char[] a3, Map<String, Boolean> cache) { if(i == a1.length && j == a2.length){ return true; }else if(i == a1.length){ return isSame(a2, j, a3, i + j); }else if(j == a2.length){ return isSame(a1, i, a3, i + j); } char c1 = a1[i]; char c2 = a2[j]; String k1 = (i + 1) + ":" + j; String k2 = i + ":" + (j + 1); if(c1 != a3[i + j] && c2 != a3[i + j]){ return false; } if(c1 == a3[i + j]){ if(!cache.containsKey(k1)){ cache.put(k1, isInterleave(a1, i + 1, a2, j, a3, cache)); } if(cache.get(k1)){ return true; } } //c2 == a3[i + j] if(!cache.containsKey(k2)){ cache.put(k2, isInterleave(a1, i, a2, j + 1, a3, cache)); } return cache.get(k2); } private boolean isSame(char[] a1, int i, char[] a2, int j){ for(int k = 0; k + i < a1.length; k++){ if(a1[i + k] != a2[j + k]){ return false; } } return true; } }