<p>You are given a positive integer <code>n</code>.</p>

<p>A binary string <code>x</code> is <strong>valid</strong> if all <span data-keyword="substring-nonempty">substrings</span> of <code>x</code> of length 2 contain <strong>at least</strong> one <code>&quot;1&quot;</code>.</p>

<p>Return all <strong>valid</strong> strings with length <code>n</code><strong>, </strong>in <em>any</em> order.</p>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 3</span></p>

<p><strong>Output:</strong> <span class="example-io">[&quot;010&quot;,&quot;011&quot;,&quot;101&quot;,&quot;110&quot;,&quot;111&quot;]</span></p>

<p><strong>Explanation:</strong></p>

<p>The valid strings of length 3 are: <code>&quot;010&quot;</code>, <code>&quot;011&quot;</code>, <code>&quot;101&quot;</code>, <code>&quot;110&quot;</code>, and <code>&quot;111&quot;</code>.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">n = 1</span></p>

<p><strong>Output:</strong> <span class="example-io">[&quot;0&quot;,&quot;1&quot;]</span></p>

<p><strong>Explanation:</strong></p>

<p>The valid strings of length 1 are: <code>&quot;0&quot;</code> and <code>&quot;1&quot;</code>.</p>
</div>

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

<ul>
	<li><code>1 &lt;= n &lt;= 18</code></li>
</ul>

class Solution:
    def validStrings(self, n: int) -> List[str]:

        dp_dict = {}
        dp_dict[1] = ["1","0"]
        for i in range(2, n+1):
            p_list = dp_dict[i-1]
            c_list = []
            for p_str in p_list:
                if(p_str[-1] == '0'):
                    c_list.append(p_str + '1')
                else:
                    c_list.append(p_str + '0')
                    c_list.append(p_str + '1')
            dp_dict[i] = c_list
        return dp_dict[n]

        q = deque([[]])
        ans = []
        while q:
            cur = q.popleft()
            if len(cur) == n:
                ans.append("".join(cur))
            else:
                if len(cur) == 0 or cur[-1] == '1':
                    q.append(cur + ['0'])
                q.append(cur + ['1'])
        return ans


        # def dfs(cur):
        #     if len(cur) == n:
        #         self.ans.append("".join(cur))
        #         return
        #     if len(cur) == 0 or cur[-1] == '1':
        #         dfs(cur + ["0"])
        #     dfs(cur + ["1"])
        
        # self.ans = []
        # dfs([])
        # return self.ans

18500