No one thinking about BFS\DFS solution ?


  • 0
    A

    I have a BFS (or DFS) solution which is hitting TLE. Not sure if it could be optimized further. Basically every character in string S is a node in the BFS graph. There is a struct which maintains the sIndex and its corresponding tIndex (in case of duplicates).

        class Solution {
    public:
        
        vector < pair <int,int> > findNeighbors(string s, string t, pair <int,int> iStruct)
        {
            vector< pair <int, int> > indexs;
            int newTIndex = iStruct.second + 1;
            
            for (int i = iStruct.first + 1; newTIndex < tLen && i < sLen; i++)
            {
                if(s[i] == t[newTIndex])
                {
                    pair<int,int> ixs = make_pair(i, newTIndex);
                    indexs.push_back(ixs);
                }
            }
            return indexs;
        }
    
        int sLen, tLen;
        int numDistinct(string s, string t) {
            
            tLen = t.length();
            sLen = s.length();
            
            if (tLen == 0)
                return 0;
            
            if (t.compare(s) == 0) 
                return 1;    
            
            queue <pair <int, int> > q;
    
            int count = 0;
            for (int i = 0; i < sLen; i++)
            {
                if(s[i] == t[0])
                {
                    pair<int,int> iStruct = make_pair(i, 0);
                    q.push(iStruct);
                }
            }
            
            while (!q.empty())
            {
                pair<int, int> iStruct = q.front();
                q.pop();
            
                if (iStruct.second == tLen - 1)
                {
                    count += 1;
                    continue;
                }
                
                vector< pair<int,int> > indexs = findNeighbors(s, t, iStruct);
                for (int i = 0; i < indexs.size(); i++)
                {
                    q.push(indexs[i]);
                }
                
            }
        
            return count;
        }
    };

  • 0

    I'm always thinking of DFS for this kind of problem. I'm bad at DP...

        private Integer[][] memo;
        
        public int numDistinct(String s, String t) {
            if (memo == null) memo = new Integer[s.length() + 1][t.length() + 1];
            if (t.isEmpty()) return 1;
            if (s.length() < t.length()) return 0;
            if (memo[s.length()][t.length()] != null) return memo[s.length()][t.length()];
            
            int num = 0;
            for (int i = 0; i <= s.length() - t.length(); i++)
                if (s.charAt(i) == t.charAt(0))
                    num += numDistinct(s.substring(i + 1), t.substring(1));
            memo[s.length()][t.length()] = num;
            return num;
        }
    

Log in to reply
 

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