Backtrack

Problem

332. Reconstruct Itinerary

Naive backtrack (TLE)

The following backtrack code got TLE

11 / 80 test cases passed.
Status:Time Limit Exceeded
class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = collections.defaultdict(list)
        N = len(tickets)+1
        for a, b in tickets:
            graph[a].append(b)
        for key in graph:graph[key].sort(reverse=True)
        res = []
        def dfs(stop, history):
            if len(history)==N:
                res.append(history)
                return
            src = history[-1]
            for i, des in enumerate(graph[src]):
                if des == 'VISITED':continue
                current_val = graph[src][i]
                graph[src][i] ='VISITED' 
                dfs(des,history+[des])
                graph[src][i] = current_val
            
        dfs('JFK', ['JFK'])  
        if len(res)==1:return res[0]
        return min(res, key=lambda x:''.join(x))

Good backtrack

The critical part is sort the graph. If the graph is in a sorted order, we can early stop if we find the first feasible path (the sorting guarantee that path is the smaller lexical order path). This can make the code get rid of TLE.

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = collections.defaultdict(list)
        N = len(tickets)+1
        for a, b in tickets:
            graph[a].append(b)
        for key in graph:graph[key].sort()
        def dfs(stop, history):
            if len(history)==N:
                return history
            src = history[-1]
            for i, des in enumerate(graph[src]):
                if des == 'VISITED':continue
                current_val = graph[src][i]
                graph[src][i] ='VISITED' 
                res = dfs(des,history+[des])
                if res is not None:return res
                graph[src][i] = current_val
            
        return dfs('JFK', ['JFK'])

Time and space complexity of this code

From the Leetcode official solution to this problem.

Code from stefan

Code from stefan

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        targets = collections.defaultdict(list)
        for a, b in sorted(tickets, reverse=True):
            targets[a].append(b)
        route = []
        def visit(airport):
            while targets[airport]:
                 visit(targets[airport].pop())
            route.append(airport)
        visit('JFK')
        return route[::-1]

212. Word Search II

Straightforward backtracking

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        words_pos = collections.defaultdict(list)
        R, C = len(board), len(board[0])
        for i in range(R):
            for j in range(C):
                words_pos[board[i][j]].append((i,j))
        def backtracking(i,j, word):
            if not word:return True
            if i<0 or i>=R or j<0 or j>=C or board[i][j]!=word[0]:return False
            word_val = board[i][j]
            board[i][j] = '#'
            res = any(backtracking(i+di, j+dj, word[1:]) for di,dj in [(0,1),(0,-1),(1,0),(-1,0)])
            board[i][j] = word_val
            return res
            
        return sorted([w for w in words if any(backtracking(i,j,w) for i, j in words_pos[w[0]])])

Backtracking and Trie got AC

_END = "_END"
class Trie:
    def __init__(self):
        self.trie = {}
    def insert(self, word):
        current_d = self.trie
        for w in word:
            current_d = current_d.setdefault(w, {})
        current_d[_END] = _END
class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        if not board or not board[0]:return []
        R, C =len(board), len(board[0])
        res, trie = set(), Trie()
        def dfs(i,j, word, current_d):
            if _END in current_d:
                res.add(word)
                
            if i<0 or i>=R or j<0 or j>=C or board[i][j] not in current_d:return
            # backtracking
            temp = board[i][j]
            current_d = current_d[temp]
            board[i][j] = "#"
            for di, dj in [(1,0),(-1,0),(0,1),(0,-1)]:
                r, c = i+di, j+dj
                dfs(r,c,word+temp,current_d)
            board[i][j] = temp   
            
        for word in words:
            trie.insert(word)
        cur_d = trie.trie
        for i in range(R):
            for j in range(C):
                dfs(i, j, "", cur_d)
        return list(res)

140. Word Break II

Backtracking got TLE

//TLE 31 / 36 test cases passed.
class Solution {
public:
    void backtrack(vector<string>& ret, int i, string& s, string curr, unordered_set<string>& words)
    {
        if (i == s.length())
        {
            ret.push_back(curr);
        }
        string new_curr;
        for (int j = i; j < s.length(); ++j)
        {
            if (words.count(s.substr(i, j - i +1)))
            {
                if (curr.empty())
                {
                    new_curr = s.substr(i, j - i +1);
                }
                else
                {
                    new_curr = curr + " " + s.substr(i, j - i +1);
                }
                backtrack(ret, j + 1, s, new_curr, words);
            }
        }
        
    }
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        vector<string> ret;
        unordered_set<string> words;
        for (auto word : wordDict) words.insert(word);
        backtrack(ret, 0, s, "", words);
        return ret;
    }
};

A recursive with memo solution can be found HERE.