Why this dfs solution got TLE?


  • 0
    H

    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;
        }
    };
    

  • 0

    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 = 3next; 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.


Log in to reply
 

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