# No one thinking about BFS\DFS solution ?

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

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

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