扰乱字符串（Java算法每日一题）

原题链接：

答：

class Solution {
          
   
    int [][][] str;
    String s1,s2;
    public boolean isScramble(String s1, String s2) {
          
   
       int length = s1.length();
       this.str = new int[length][length][length+1];//length是s1,s2字符串的长度
       this.s1 = s1;
       this.s2 = s2;
       return judge(0,0,length);
    }
    public boolean judge(int i,int j,int length)
    {
          
   
        if(str[i][j][length] != 0)
            return str[i][j][length] == 1;
        //判断两个字符串是否相等
        if(s1.substring(i,i+length).equals(s2.substring(j,j+length)))
        {
          
   
            str[i][j][length] = 1;
            return true;
        }
        if(!check(i,j,length))
        {
          
   
            str[i][j][length] = -1;
             return false;
        }
        for(int p = 1;p < length;p++)
        {
          
   
            
            //不交换
            if(judge(i,j,p)&&judge(i+p,j+p,length-p))
            {
          
   
                str[i][j][length] = 1;
                return true;
            }
                
            //交换
            if(judge(i,j+length-p,p)&&judge(i+p,j,length-p))
            {
          
   
                str[i][j][length] = 1;
                return true;
            }
        }
        str[i][j][length] = -1;
        return false;

    }
    //判断字符串出现的次数是否相同
    public boolean check(int i,int j,int length)
    {
          
   
        Map<Character,Integer> map = new HashMap<Character,Integer>();
        for(int k = i; k < i + length;k++)
        {
          
   
            char ch = s1.charAt(k);
            map.put(ch, map.getOrDefault(ch, 0) + 1);//如果存在改字符就返回对应的value,否则返回默认值0
        }
        for(int k = j; k< j + length;k++)
        {
          
   
            char ch = s2.charAt(k);
            map.put(ch, map.getOrDefault(ch, 0) - 1);//如果存在改字符就返回对应的value,否则返回默认值0
        }
        for (Map.Entry<Character,Integer> entry : map.entrySet())
        {
          
      
            int v = entry.getValue();
            if(v != 0)
            {
          
   
                return false;
            }
        }
        return true;
    }   
}