# Why this dfs solution got TLE?

• I think time complexity of this DFS solution is also O(m * n)，as O(m * n) DP solution is accepted, this solution got TLE, Could anyone explain why to me? Thanks in advance.

``````class Solution {
public:
int ans = 0;
void dfs(string s, int s_idx, string t, int t_idx) {
//cout << s_idx << ", " << t_idx << endl;
if(t_idx == t.size()) {
ans ++;
return;
}
if(s_idx == s.size()) return;
if(s[s_idx] == t[t_idx]) // if match, 2 options: choose or not choose
dfs(s, s_idx + 1, t, t_idx + 1);
dfs(s, s_idx + 1, t, t_idx); // search next, no matter match or not
}
int numDistinct(string s, string t) {
if(s.size() < t.size()) return ans;
dfs(s, 0, t, 0);
return ans;
}
};
``````

• I'm giving you an example where your solution costs more time than DP.

Consider `S = "rabbbit"` and `T = "rabbit"`.

In your solution, when `s_idx = 4` and `t_idx = 3`, we will choose and not choose the character `'b'` at "rabbbit".

When we choose the character b, we will consider `s_idx = 5, t_idx = 4` next; then if we not to choose the next b, we got to `s_idx = 6, t_idx = 4`.

And when we not choose the character b, we will consider `s_idx = 5, t_idx = 3`next; then if we choose the next b, we got to `s_idx = 6, t_idx = 4`, again.

You may buffer the result in a 2-dim array so your solution will be significantly quicker.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.