thảo luận [Học Tập] Topic thuật toán

def func(inputStr):
    return sum(int(x) for x in inputStr if x.isdigit())

#include <queue>
#include <list>

class Solution {
public:
    struct Node
    {
        std::string str;
        int value = -1;
        
        bool visited = false;
        
        std::list<Node*> adj;
    };
    
    bool match(const string& str1, const string& str2)
    {
        int count = 0;
        
        for(int i = 0; i < str1.size(); ++i)
        {
            if(str1[i] != str2[i])
                count++;
        }
        
        return count <= 1;
    }
    
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {

        std::list<Node*> list;
        
        Node* begin = new Node;
        begin->str = beginWord;
        begin->value = -1;
        begin->visited = false;
        
        list.push_back(begin);
        
        for(const auto& iter : wordList)
        {
            if(iter == beginWord)
                continue;
            
            Node* node = new Node;
            node->str = iter;
            node->value = -1;
            node->visited = false;
            
            list.push_back(node);
        }
        
        for(const auto& iter : list)
        {
            for(const auto& iterInner : list)
            {
                if(iter != iterInner && match(iter->str, iterInner->str))
                {
                    iter->adj.push_back(iterInner);
                }
            }
        }
        
        std::queue<Node*> queue;
        begin->value = 1;
        queue.push(begin);
        
        while(!queue.empty())
        {
            Node* node = queue.front();
            queue.pop();
            
            if(node->visited)
                continue;
            
            node->visited = true;
            
            for(auto& iter : node->adj)
            {
                if(iter->visited)
                    continue;
                
                if(iter->value == -1)
                {
                    iter->value = node->value + 1;
                }
                else
                {
                    iter->value = std::min(iter->value, node->value + 1);
                }
                
                queue.push(iter);
            }
            
        }
        
        int nRet = 0;
        
        for(auto& iter : list)
        {
            if(iter->str == endWord)
            {
                nRet = iter->value;
                break;
            }
        }
        
        for(auto& iter : list)
        {
            if(iter)
            {
                delete iter;
                iter = nullptr;
            }
        }
        
        list.clear();       
        
        return nRet < 0 ? 0 : nRet;
    }
};