Just to use DFS, HashMap


  • 1
    V

    The runtime isnt great though..

    public class Solution 
    {
        HashMap<String, Integer> hm;
        public int numDistinct(String s, String t) 
        {
            hm = new HashMap<String, Integer>();
            return dfs(s, 0, t, 0);
        }
        int dfs(String s, int i1, String t, int i2)
        {
            String temp = "s" + i1 + "t" + i2;
            if(hm.containsKey(temp))
                return hm.get(temp);
            if(i2 == t.length())
                return 1;
            int cnt = 0;
            for(int i = i1; i < s.length(); i++)
            {
                if(s.charAt(i) == t.charAt(i2))
                    cnt += dfs(s, i + 1, t, i2 + 1);
            }
            hm.put(temp, cnt);
            return cnt;
        }
    }

Log in to reply
 

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