文字列変換

文字列変換

leetcode  6    

タイトル
同じ長さの2つの文字列が与えられ、それぞれstr1とstr2である.文字列str1がゼロまたは複数回変換された後に文字列str2になるかどうかを判断してください.
変換のたびに、str1に表示されるすべての同じアルファベットが、他の任意の小文字のアルファベットに一度に変更されます(例を参照).str1は、文字列str2が上記のように文字列Trueに順調に変換された場合にのみ返され、そうでなければFalseに返される.​​
例1:

  ：str1 = "aabcc", str2 = "ccdee"
  ：true
  ：  'c'    'e'，    'b'    'd'，     'a'    'c'。  ，         。

例2:

  ：str1 = "leetcode", str2 = "codeleet"
  ：false
  ：          str1     str2。


  ：

1 <= str1.length == str2.length <= 10^4
str1   str2              

問題を解く構想.

の主な考え方は、HashMapを確立し、現在の文字列の情報をmapに格納することである.

例:HashMapこのときmap 1内の内容は:

である.
key
value
a
0、1
b
2
c
3、4

map2     :

key
value
c
0、1
d
2
e
3、4
このとき、keyのうちの(a ~ z)、すなわちvalueを遍歴する、第1のグループのうちのHashSetは、まずstr1 = "aabcc", str2 = "ccdee"であり、この下付き文字に基づいてstr 1の対応する位置の文字、すなわちmap2が見つかる、このときの文字はvalueであり、set1によってmap 1中の文字0、1の下付き文字の集合0が見つかる、次に、このセットがstr1.charAt(0);のサブセットであるか否かを判断する.そうでなければ、変換が完了せずに遍歴した後、いずれも満足し、aに戻る

とは、a(key）のいずれかの文字が、aの対応する位置の1つまたは複数の文字から変換されなければならず、set2のこれらの文字は、他の文字に変換するために使用できないことを意味する.例えば、set1 trueはtrueを出力する.

str2の文字の種類がstr1である場合、str1がstr1="abcde"に等しくない限り、変換は完了する、例えば、str2="eeexy" str2 26

.

class Solution {
    public boolean canConvert(String str1, String str2) {
        //           ,    false
        if (str1.isEmpty()|| str2.isEmpty() || str1.length() != str2.length()) return false;
        //             true
        if (str1.equals(str2)) return true;

        //             map
        HashMap<Character,HashSet<Integer>> map1 = initialize(str1);
        HashMap<Character,HashSet<Integer>> map2 = initialize(str2);
        //      map size ,             
        int num1 = map1.size();
        int num2 = map2.size();
        //  str1         str2,  str2        26,
        //        ,            ,       
        if (num1 < num2 || num2 == 26) return false;
        //  map2    (value)
        for (HashSet<Integer> value : map2.values()) {
            //    set   
            for (Integer n : value) {
                //  str2   str1       c
                Character c = str1.charAt(n);
                // map1     c        set
                HashSet<Integer> set = map1.get(c);
                //  set          value
                //   ,   false
                if (!isOnly(value,set)) {
                    return false;
                }
            }
        }

        return true;
    }

    /**
     *             map
     *  HashMap   key      (a~z),
     * value       ,            , HashSet  
     * @param str
     * @return
     */
    public HashMap<Character,HashSet<Integer>> initialize(String str) {
        HashMap<Character,HashSet<Integer>> map = new HashMap<>();
        for (int i = 0; i < str.length(); i++) {
            Character c = str.charAt(i);
            if (map.containsKey(str.charAt(i))) {
                HashSet<Integer> set = map.get(c);
                set.add(i);
                map.put(c, set);
            } else {
                HashSet<Integer> set = new HashSet<>();
                set.add(i);
                map.put(c, set);
            }
        }
        return map;
    }

    /**
     *   set1          set2
     *     set1     set2    
     *    ,   false
     * @param set2
     * @param set1
     * @return
     */
    public boolean isOnly(HashSet<Integer> set2,HashSet<Integer> set1){
        boolean is = true;
        for (Integer n : set1) {
            if (!set2.contains(n)){
                is = false;
            }
        }
        return is;
    }
}