coder_of_india.'s blog

By coder_of_india., history, 6 months ago, In English


#include <bits/stdc++.h> using namespace std; struct Node { vector<Node*> child ; bool is ; Node() { child.resize(26 , NULL) ; is = false; } }; class Trie{ Node *root ; public: Trie() { root = new Node() ; } void insert(string s) { Node *cur = root ; int i = 0 ; while(i < s.length()) { if(cur -> child[s[i] - 'a'] == NULL) cur -> child[s[i] - 'a'] = new Node(); cur = cur -> child[s[i] - 'a'] ; i ++ ; } cur -> is = true ; } void search(string &s ,int st , vector<bool> &dp) { Node *cur = root ; for(int i = st ; i < s.length() ; i ++ ) { if(cur == NULL) return ; cur = cur -> child[s[i] - 'a'] ; if(cur && cur -> is ) dp[i + 1] = true ; } } }; class Solution{ public: int wordBreak(string A, vector<string> &B) { //code here Trie *tmp = new Trie(); int n = A.size() ; vector<bool> dp(n + 1, false) ; for(int i =0 ; i < B.size() ; i ++ ) tmp -> insert(B[i]) ; dp[0] = true ; for(int i = 0 ; i < A.length() ; i ++ ) { if(dp[i]) tmp -> search( A , i , dp) ; } return dp[n]; } }; int main(){ int t; cin>>t; while(t--){ int n; cin>>n; vector<string> dict; for(int i=0;i<n;i++){ string S; cin>>S; dict.push_back(S); } string line; cin>>line; Solution ob; cout<<ob.wordBreak(line, dict)<<"\n"; } }

Read more »

 
 
 
 
  • Vote: I like it
  • -26
  • Vote: I do not like it

By coder_of_india., history, 14 months ago, In English

*****************************************************TLE CODE *************************************************************

int dx[4] = {0 , -1 , 0 , 1} ; . int dy[4] = {-1 , 0 , 1 , 0} ;
``````
bool checker (vector<vector> grid , int i , int j , int n , int m )
{
if(i >= 0 && i < n && j >= 0 && j < m && ( grid[i][j] == '1'))
return true;
return false;
}

void dfs(vector<vector> &grid , int i , int j ,int r , int c) {

grid[i][j] = '0';
for(int k = 0 ; k < 4 ; k ++ )
{
    int newx = i + dx[k] ;
    int newy = j + dy[k] ;
    if( checker(grid , newx , newy , r , c)  ) 
    {    
        grid[newx][newy] = '0';
        dfs(grid , newx , newy , r , c);
    }
}

} class Solution { public: int numIslands(vector<vector>& grid) {

int r = grid.size() ;
    int c = grid[0].size() ;
    int cnt = 0 ;
    for(int i = 0 ; i < r ; i ++ )
    {
        for(int j = 0 ; j < c ; j ++ ) 
        {
              if(grid[i][j] == '1') 
              {
                  cnt ++ ; 
                  dfs(grid , i , j ,r , c);
              }
        }
    }
    return cnt ;
}

};

************************************************** AC CODE *******************************************************************

int dx[4] = {0 , -1 , 0 , 1} ; int dy[4] = {-1 , 0 , 1 , 0} ;

void dfs(vector<vector> &grid , int i , int j ,int r , int c) {

grid[i][j] = '0';
for(int k = 0 ; k < 4 ; k ++ )
{
    int newx = i + dx[k] ;
    int newy = j + dy[k] ;
    if(newx >= 0 && newx < r && newy >= 0 && newy < c && ( grid[newx][newy] == '1')) 
    {    
        grid[newx][newy] = '0';
        dfs(grid , newx , newy , r , c);
    }
}

} class Solution { public: int numIslands(vector<vector>& grid) {

int r = grid.size() ;
    int c = grid[0].size() ;
    int cnt = 0 ;
    for(int i = 0 ; i < r ; i ++ )
    {
        for(int j = 0 ; j < c ; j ++ ) 
        {
              if(grid[i][j] == '1') 
              {
                  cnt ++ ; 
                  dfs(grid , i , j ,r , c);
              }
        }
    }
    return cnt ;
}

}; ******************************************************************************************************************************

Both codes are same but there is one difference I used cheacker function that's why i am getting tle why this is happening ? please tell me anyone.

Thanks in advance !!

Read more »

 
 
 
 
  • Vote: I like it
  • -12
  • Vote: I do not like it