# I want to optimize my solution with some better idea rather than this tricky method.Anyone can help?

• actually, i got an accepted using a solution which has the O(n^3) time-complexity . of course there is a tricky method in it. Is there anybody could help me to reduce its time-complexity?THANKS.
comment:DP[i][j] is a bool array which means whether we can make a matching in that dictionary using s[i~j].

``````class Solution {
public:
list <string> seg;
bool dp[500][500];
void recursion(int left, int right, string s, int len, vector<string> &ans)
{
if (right == len-1){
string per_ans = "";
for (list<string> :: iterator it = seg.begin(); it != seg.end(); it ++){
if (it != seg.begin())per_ans += " ";
per_ans += (*it);
}
ans.push_back(per_ans);
}
for (int i = right+1; i < len; i ++){
if (dp[right+1][i]){
seg.push_back(s.substr(right+1, i-right));
recursion(right+1, i, s, len, ans);
seg.pop_back();
}
}
}

vector<string> wordBreak(string s, unordered_set<string> &dict) {
int len = s.length();
vector<string> ans;
ans.clear();
for (int i = 0; i < len; i ++){
for (int j = 0; j < len; j ++)  dp[i][j] = false;
if (dict.find(s.substr(0,i+1)) != dict.end())dp[0][i] = true;
}
for (int i = 0; i < s.length(); i ++){
for (int j = 0; j < len; j ++){
if (dp[i][j]){
for (int k = j+1; k < len; k ++){
if (dp[j+1][k] == false && dict.find(s.substr(j+1, k-j)) != dict.end())dp[j+1][k] = true;
}
}
}
}
bool jud = true;//so tricky, if there has no matching of dictionary return the initial vector
for (int i = 0; i < len && jud; i ++){
if (dp[i][len-1])jud = false;
}
if (jud)return ans;
for (int i = 0; i < len; i ++){
if (dp[0][i]){
seg.push_back(s.substr(0,i+1));
recursion(0,i,s,len,ans);
seg.pop_back();
}
}
return ans;
}
};``````

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