c++ 6ms solution


  • 0
    L

    class Solution {
    public:
    struct TireNode
    {
    TireNode *pNext[26];
    bool bWord;
    TireNode():bWord(false){memset (pNext,0,sizeof(pNext));}
    ~TireNode(){}
    };
    class TrieTree
    {
    public:
    TrieTree(){m_pRoot=new TireNode();}
    ~TrieTree(){}
    void Insert(string &str)
    {
    TireNode *pNode=m_pRoot;
    for(size_t i=0;i<str.size();++i)
    {
    int nPos=str[i]-'a';
    if(pNode->pNext[nPos]==NULL)
    {
    pNode->pNext[nPos]=new TireNode();
    }
    pNode=pNode->pNext[nPos];
    }
    pNode->bWord=true;
    }
    TireNode *Find(TireNode *pNode,char word)
    {
    TireNode *pTemp=NULL;
    if(pNode!=NULL)
    {
    pTemp=pNode->pNext[word-'a'];
    }
    return pTemp;
    }
    TireNode *GetRoot()
    {
    return m_pRoot;
    }
    void FreeTire(TireNode *pNode)
    {
    if(pNode==NULL)
    return;
    for(int i=0;i<26;++i)
    {
    if(pNode->pNext[i]!=NULL)
    {
    FreeTire(pNode->pNext[i]);
    }
    }
    delete pNode;
    }
    private:
    TireNode *m_pRoot;

    };

    vector<string> wordBreak(string &s, vector<string>& wordDict) 
    {
        for(size_t i=0;i<wordDict.size();++i)
        {
            tree.Insert(wordDict[i]);
        }
        vector<vector<string> > vResult(s.size());
        GetResult(vResult,s,0);
        if(vResult[0][0].empty())
        {
            return vector<string>();
        }
        return vResult[0];
    }
    
    void    GetResult(vector<vector<string> >& vResult,string &str,size_t nBeginPos)
    {
        if(nBeginPos==str.size())
        {
            return ;
        }
        TireNode *pNode= tree.GetRoot();
        for(size_t nCurPos=nBeginPos;nCurPos<str.size();++nCurPos)
        {
            pNode=tree.Find(pNode,str[nCurPos]);
            if(pNode==NULL)
            {
                break;
            }
            if(pNode->bWord)
            {
                if(nCurPos+1==str.size())
                {
                    vResult[nBeginPos].push_back(str.substr(nBeginPos));
                    return;
                }
                else
                {
                    if(vResult[nCurPos+1].empty())
                    {
                        GetResult(vResult,str,nCurPos+1);
                    }
                    if(vResult[nCurPos+1][0].empty())
                    {
                        continue ;
                    }
                    for(size_t i=0;i<vResult[nCurPos+1].size();++i)
                    {
                        vResult[nBeginPos].push_back(str.substr(nBeginPos,nCurPos+1-nBeginPos)+" "+vResult[nCurPos+1][i]);
                    }
                    
                }
                
            }
        }
        if(vResult[nBeginPos].empty())
        {
            vResult[nBeginPos].push_back(string());
        }
    }
    TrieTree tree;
    

    };


Log in to reply
 

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