Word Break | Leetcode | Medium | Java | Striver's A to Z DSA Sheet | Recursion

This problem is a pretty popular one if you're practicing recursion and is also a part of Striver's A to Z DSA sheet. Well, this problem requires us to optimize the solution using DP otherwise the solution results in TLE when submitting on leetcode.

Other problems for practice:

[atulwadhwa]

Thanks for the video Aditi, because of your video I realised why it's a dp problem and more importantly how we can optimize it.
1-D dp solution [C++] [Memoization]

class Solution{
private:
bool solve(int ind, string &s, int str_len, unordered_map<string, int> &mp, vector<int> &dp){
if(ind==str_len)
return true;

if(dp[ind]!=-1)
return dp[ind];

for(int i=ind;i<str_len;i++){
if(mp.find(s.substr(ind, i-ind+1))!=mp.end()){
if(solve(i+1, s, str_len, mp, dp))
return dp[ind]=true;
}
}
return dp[ind]=false;
}
public:
bool wordBreak(string s, vector<string>& wordDict) {
int size=wordDict.size();
unordered_map<string, int> mp;
for(int i=0;i<size;i++)
mp[wordDict[i]]=1;
int str_len=s.size();
vector<int> dp(str_len+1, -1);
return solve(0, s, str_len, mp, dp);
}
};
PS: You can convert it to tabulation to eliminate aux stack space

[ashuyadav]

hello Aditi, here is c++ code with 2D dp
note: s.substr(start, length): this function take length instead of end in c++,
class Solution {
public:
bool solve(int start, int end, string &s, set<string> &wD, vector<vector<int>> &dp){

if(dp[start][end]!=-1){
return dp[start][end]==1 ?true:false;
}

if(end==s.length()-1){
if(wD.contains(s.substr(start, end - start + 1))){
dp[start][end] = 1;
return true;
}
return false;
}

if(wD.contains(s.substr(start, end - start + 1))){
if(solve(end+1, end+1, s, wD, dp)) {
dp[start][end]=1;
return true;
}
}
bool ans=solve(start, end+1, s, wD, dp);
dp[start][end]= ans ? 1:0;
return ans;
}


bool wordBreak(string s, vector<string>& wordDict) {
set<string>wd(wordDict.begin(), wordDict.end());
vector<vector<int>> dp(s.length(), vector<int>(s.length(), -1));
return solve(0, 0, s, wd, dp);
}
};

[ritikshandilya]

Amazing solution, Thanks for making this video

[samrat_malisetti]

I have gone through several videos about this problem. But I didn't find the solution that you explained. Great video :)

[ChaithanyaGanesh_India]

class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int [][]dp= new int [s.length()][s.length()];
for(int i=0;i<s.length();i++){
for(int j=0;j<s.length();j++){
dp[i][j]=-1;
}
}
return fns(0, 0, s, new HashSet(wordDict), dp );
}

public boolean fns(int start, int end, String s, Set<String> wd, int [][]dp){
if (start > end || end >= s.length()) {
return false;
}

if(dp[start][end]!=-1){
return dp[start][end]==1;
}


if(wd.contains(s.substring(start, end+1))){
if(end==s.length()-1 || fns(end+1, end+1, s, wd, dp)){
dp[start][end]=1;
return true;
}
}

boolean ans=fns(start, end+1, s, wd, dp);

dp[start][end]=ans? 1:0;

return ans;
}
}

[aditipatil]

make more vdios youur explanation is amazing

[Manpreetkaur-xrcg]

one side of tree(0, 6) returns false and other (5, 9) returns true, which one will be considered

[theashutoshgupta_yt]

why dont we take "wordDict" and traverse them to from "string s" like leet+code = leetcode, apple+dogs+apple =appledogapple, since this was in recursion section i avoided going in DP here.

droping the code here, review it as it is giving TLE after 32/46 testcases


class Solution {
private:
bool flag = false;
void solve(vector<string>& wordDict, int index, string st, string temp){
// cout<<temp<<endl;
if(temp.size()>st.size()){

return;
}
if(temp==st){
flag = true;
return;
}

for(int i=0;i<wordDict.size();i++){
if(temp.size()<st.size())
solve(wordDict, i+1, st, temp+wordDict[i]);
}
}
public:
bool wordBreak(string s, vector<string>& wordDict) {
solve(wordDict, 0, s, "");
return flag;
}
};

[saurabhrthakur]

Hey Aditi I am getting problem in this, because public function is taking vector as argument, and we are giving 'set' in the private function

[ultimatescience]

Hey!
I am in my third year and still don't have any idea about coding.
I am thinking of doing DSA with c++ but don't know where and how to start. Also, striver's DSA playlist is not complete.
Can you please guide me?
I am planning and trying to get off-campus placement in a product-based company.