C++ DFS solution with explanation


  • 5
    L

    class Solution {
    public:

    vector<string> generateAbbreviations(string word)
    {
    
    	vector<string> res;
    
    	// using dfs to generate
    	function<void(string, int, bool)> dfs = [&](string s, int index, bool isnum)
    	{
    		
    		if (index == word.size()) //case of when a path is finshed
    		{
    			res.push_back(s);
    			return;
    		}
    		else
    		{
    			//every charactor is whether selected or not,
    			dfs(s + word[index], index + 1, false); // here is selected
    
    			//isnums true, means previous charactor has been number, here ignored to avoid the case like w11d of word, it should be w2d
    			if (!isnum)
    			{
    				int len = 1; // iterate all possible length;
    				while (len <= word.size() - index)
    				{
    					dfs(s + to_string(len), index + len, true);
    					len++;
    				}
    			}
    		}
    	};
    	string s;
    	dfs(s, 0, false);
    	return res;
    }
    

    };


  • 0
    I

    Can you explain some of this syntax?

     function<void(string, int, bool)> dfs = [&](string s, int index, bool isnum)
    

    I see that std::function is being used here. What is the [&] for?


  • 0
    L

    it's a capture list for the C++ lambda. It means capture the variable outside lambda by reference.


Log in to reply
 

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