Find the minimum steps required to change one binary string to another

Question

Given the two lines str1 and str2 that contain only 0or 1, there are some steps for changing str1 to str2,

step1: find the substring str1 of length 2 and change the substring, and str1 becomes str1 '(str1'! = str1)

step2: find the substring str1 'of length 3 and change the substring, and str1' will become str1 '' (str1 ''! = str1 ')

The following steps are similar.

string length is in the range [2, 30]

Requirement : each step must be performed once, and we cannot skip the previous steps and complete the next step.

If you can change str1 to str2, print the required minimum steps, otherwise print -1

Example 1

str1 = "1010" , str2 = "0011", 2

[2, 3], "1010" → "1001" ,

[0, 2], "1001" → "0011"

2

str1 = "1001" , str2 = "0110", str1 str2, 1 str1 "0101" "1010" , 3 length3, . , -1.

3

str1 = "10101010", str2 = "00101011", 7

3, . - , ? ? ?

Answer 1

. , , . , - 2^30 30, , , , 30 choose 15 = 155117520 15 . 150 - .

, start , , , end . , . :

start = '10101010'
end = '00101011'

dp = [{} for _ in range(31)]
dp[1][start] = '' # Originally only start string is reachable

for i in range(2, len(start) + 1):
  for s in dp[i - 1].keys():
    # Try all possible reversals for each string in dp[i - 1]
    for j in range(len(start) - i + 1):
      newstr = s
      newstr = newstr[:j] + newstr[j:j+i][::-1] + newstr[j+i:]
      dp[i][newstr] = s
  if end in dp[i]:
    ans = []
    cur = end
    for j in range(i, 0, -1):
      ans.append(cur)
      cur = dp[j][cur]
    print(ans[::-1])
    exit(0)

print('Impossible!')

['10101010', '10101001', '10101100', '10100011', '00101011'] - str1 str2. , , . , 4 , 7, .

, 30 python, C++, .

Answer 2

. , , ( 2) . , . k, k - , , . , " length-2". , .

string str1,str2;
cin>>str1>>str2;

queue<pair<string, int>> q;
set<string> s;

q.push({str1,2});
s.insert(str1);
while(!q.empty())
{
    auto p=q.front();
    q.pop();
    if(p.first==str2)
    {
        cout<<p.second-2;
        return 0;
    }
    if(p.second<=p.first.size())
    {
        for(int i=0;i<=p.first.size()-p.second;i++)
        {
            string x=p.first;
            reverse(x.begin()+i,x.begin()+i+p.second);
            if(s.find(x)==s.end())
            {
                q.push({x,p.second+1});
                s.insert(x);
            }

        }
    }
}
cout<<-1;