Building a specified patterns

Some problems can be solved by building a specified patterns instead of naive brute force.

906. Super Palindromes

https://leetcode.com/contest/weekly-contest-102/problems/super-palindromes/

This code is translated from a C++ code.
https://www.cnblogs.com/grandyang/p/11204481.html
Basic idea is:
build even length plaindrome by using:
cur = c+””+c for c in “0123456789”
repeating to expand
we will have something like this:
00
11
…
99
0+00+0
1+00+1
…
9+00+9
0+11+0
1+11+1
…
9+11+9

build odd length plaindrome by using:
for s in “0123456789”:
for c in “0123456789”
new_s = c + s +c
we will have something like this:
0
0+0+0
1+0+1
…
9+0+9
0+000+0
1+000+1
…
9+000+9
…
C++ code from the post is 924 ms.
python version is 2256 ms

class Solution:
    def superpalindromesInRange(self, L: str, R: str) -> int:
        def is_plaindrome(s):return s == s[::-1]
        
        def helper(cur, l, r, res):
            if len(cur)>9:return res
            if cur and cur[0]!='0':
                num = int(cur)
                num *= num
                if num > r:return res
                if num>=l and is_plaindrome(str(num)):
                    res += 1
            for c in "0123456789":
                res = helper(c+cur+c, l, r, res)
            return res
        
        res = 0
        l, r = int(L), int(R)
        res = helper("", l, r, res)
        for c in "0123456789":
            res = helper(c, l, r, res)
        return res

We can also change the above code into DFS/BFS.

DFS(2296ms)

class Solution:
    def superpalindromesInRange(self, L: str, R: str) -> int:
        def dfs():
            digs = "0123456789"
            open_list = [""]+list(digs)
            res = 0
            while open_list:
                c = open_list.pop()
                if c and len(c)<=9:
                    c_squ = int(c)**2
                    if c[0]!=0 and int(L)<=c_squ<=int(R):
                        if str(c_squ)==str(c_squ)[::-1]:res += 1
                for d in digs:
                    nex = d+c+d
                    if len(nex)<=9 and (int(nex)**2)<=int(R):
                        open_list.append(d+c+d)
            return res
        return dfs()

Another C++ code from the submitted code is:

This code is faster, it only takes 216ms.

typedef long long ll;
class Solution {
public:
    int superpalindromesInRange(string L, string R) {
        ll l=stoll(L), r=stoll(R);
        int ans=0;
        for(int n=1;n<100000;n++)
            for(int p=0;p<2;p++){
                if(n>=10000&&p==0)continue;
                ll t=n,palin=n;
                if(p==1)t/=10;
                while(t>0){
                    palin=palin*10+t%10;
                    t/=10;
                }
                palin*=palin;
                if(palin<l||palin>r)continue;
                string s=to_string(palin);
                bool ok=true;
                for(int i=0;i<s.size()/2;i++)
                    if(s[i]!=s[s.size()-1-i]){
                        ok=false;
                        break;
                    }
                if(ok)ans++;
            }
        return ans;
    }
};

Translate to python got TLE

class Solution:
    def superpalindromesInRange(self, L: str, R: str) -> int:
        def is_palin(s):return s==s[::-1]
        l, r =int(L), int(R)
        ans=0
        for n in range(1, 100000):
            for p in range(2):
                if p==0 and n>10000:continue
                t, palin = n, n
                if p==1: t//=10
                while t>0:
                    palin = palin*10+t%10
                    t //= 10
                palin *= palin
                if palin<l or palin>r:continue
                if is_palin(str(palin)):ans+=1
        return ans

899. Orderly Queue

Orderly Queue - LeetCode

“Actually, when K>=2, we can prove that we can use the first 2 elements as a buffer to swap any two adjacent characters. Since we can reach any permutation by swapping adjacent characters (like bubble sort), in this case the minimal reachable permutation is the sorted S.

Assume that we want to swap S[i] and S[i+1], we can first pop first i-1 characters to the end, then pop i+1 and i, finally pop i+2~end.

Example:
K=2 S=bacdb Assume that we want to swap S[1] = a and S[2] = c

bacdb // initial
acdbb // pop first b to the end
dbbca // first pop S[2]=c, then pop S[1]=a
bbcad // pop S[3] = d
bcadb // pop S[4] = b, a and c are swapped!

“

https://leetcode.com/problems/orderly-queue/discuss/165878/C++JavaPython-Sort-String-or-Rotate-String/171416