<p>You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: <code>&#39;0&#39;, &#39;1&#39;, &#39;2&#39;, &#39;3&#39;, &#39;4&#39;, &#39;5&#39;, &#39;6&#39;, &#39;7&#39;, &#39;8&#39;, &#39;9&#39;</code>. The wheels can rotate freely and wrap around: for example we can turn <code>&#39;9&#39;</code> to be <code>&#39;0&#39;</code>, or <code>&#39;0&#39;</code> to be <code>&#39;9&#39;</code>. Each move consists of turning one wheel one slot.</p>

<p>The lock initially starts at <code>&#39;0000&#39;</code>, a string representing the state of the 4 wheels.</p>

<p>You are given a list of <code>deadends</code> dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.</p>

<p>Given a <code>target</code> representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> deadends = [&quot;0201&quot;,&quot;0101&quot;,&quot;0102&quot;,&quot;1212&quot;,&quot;2002&quot;], target = &quot;0202&quot;
<strong>Output:</strong> 6
<strong>Explanation:</strong> 
A sequence of valid moves would be &quot;0000&quot; -&gt; &quot;1000&quot; -&gt; &quot;1100&quot; -&gt; &quot;1200&quot; -&gt; &quot;1201&quot; -&gt; &quot;1202&quot; -&gt; &quot;0202&quot;.
Note that a sequence like &quot;0000&quot; -&gt; &quot;0001&quot; -&gt; &quot;0002&quot; -&gt; &quot;0102&quot; -&gt; &quot;0202&quot; would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end &quot;0102&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> deadends = [&quot;8888&quot;], target = &quot;0009&quot;
<strong>Output:</strong> 1
<strong>Explanation:</strong> We can turn the last wheel in reverse to move from &quot;0000&quot; -&gt; &quot;0009&quot;.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> deadends = [&quot;8887&quot;,&quot;8889&quot;,&quot;8878&quot;,&quot;8898&quot;,&quot;8788&quot;,&quot;8988&quot;,&quot;7888&quot;,&quot;9888&quot;], target = &quot;8888&quot;
<strong>Output:</strong> -1
<strong>Explanation:</strong> We cannot reach the target without getting stuck.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= deadends.length &lt;= 500</code></li>
	<li><code>deadends[i].length == 4</code></li>
	<li><code>target.length == 4</code></li>
	<li>target <strong>will not be</strong> in the list <code>deadends</code>.</li>
	<li><code>target</code> and <code>deadends[i]</code> consist of digits only.</li>
</ul>

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        return openLock_BFS(deadends, target);
        // return openLock_DFS(deadends, target);
    }

    int openLock_DFS(vector<string>& deadends, string target) {  // TLE
        vector<int> memo(10000, -1);  // memorize distances for node after it is processed
        vector<bool> processed(10000, false);  // lock ancestor nodes during dfs
        for (const string& de : deadends) processed[stoi(de)] = true;
        if (processed[0]) return -1;  // deadend, unable to rotate
        if (stoi(target) == 0) return 0;  // already with the target, no need to rotate
        memo[stoi(target)] = 0;
        processed[stoi(target)] = true;
        return dfs("0000", processed, target, memo);
    }

    // DFS is unsuitable for finding the shortest path because for each node we need to dfs to all 
    // its neighbors and compute the minimum of dist(neibor) to get dist(node). In worse case each 
    // dfs may traverse O(|V|)=O(n^w) to find the target. And time complexity will be O(|V|*|E|)=O(n^w * n^w * 2w)
    // TC: O( n^(2w) * 2w ), SC: O(n^w) for memo and recursion stack
    int dfs(string&& currState, vector<bool>& processed, const string& target, vector<int>& memo) {
        auto nextDigit = [](char c) -> char { return (c - '0' + 1) % 10 + '0'; };
        auto prevDigit = [](char c) -> char { return (c - '0' + 9) % 10 + '0'; };
        if (processed[stoi(currState)]) return memo[stoi(currState)];
        processed[stoi(currState)] = true;  // lock
        int minSteps = INT_MAX, steps = -1;
        for (int i = 0; i < currState.length(); i++) {
            char c = currState[i];
            // test next digit
            currState[i] = nextDigit(c);
            steps = dfs(move(currState), processed, target, memo);
            if (steps != -1) minSteps = min(minSteps, steps + 1);
            // test previous digit
            currState[i] = prevDigit(c);
            steps = dfs(move(currState), processed, target, memo);
            if (steps != -1) minSteps = min(minSteps, steps + 1);
            // restore
            currState[i] = c;
        }
        if (minSteps == INT_MAX) processed[stoi(currState)] = false;  // no path to target yet, unlock
        return memo[stoi(currState)] = (minSteps == INT_MAX ? -1 : minSteps);
    }

    // TC: O(|V|+|E|) = O(n^w + n^w * 2w) = O(n^w * w) = O(10^4 * 4)
    // SC: O(|V|) = O(n^w) = O(10^4)
    int openLock_BFS(vector<string>& deadends, string target) {
        vector<bool> visited(10000, false);
        for (const string& de : deadends) visited[stoi(de)] = true;
        if (visited[0]) return -1;  // deadend, unable to rotate
        if (stoi(target) == 0) return 0;  // already with the target, no need to rotate
        auto nextDigit = [](char c) -> char { return (c - '0' + 1) % 10 + '0'; };
        auto prevDigit = [](char c) -> char { return (c - '0' + 9) % 10 + '0'; };
        queue<string> q;  // nodes in the path to target, so deadends should not be put in
        q.push("0000");
        int step = 0;
        while (!q.empty()) {
            step++;
            int sz = q.size();
            while (sz--) {
                string node = q.front(); q.pop();
                for (int i = 0; i < node.length(); i++) {
                    char c = node[i];
                    node[i] = nextDigit(c);
                    if (!visited[stoi(node)]) {
                        if (node == target) return step;
                        q.push(node);
                        visited[stoi(node)] = true;
                    }
                    node[i] = prevDigit(c);
                    if (!visited[stoi(node)]) {
                        if (node == target) return step;
                        q.push(node);
                        visited[stoi(node)] = true;
                    }
                    node[i] = c;
                }
            }
        }
        return -1;
    }
};
19640