Merge pull request SharingSource#505 from SharingSource/ac_oier

SharingSource · web-flow · commit 4db0d335182e · 2022-05-07T15:27:35.000+08:00
&#10024;feat: Add 433
diff --git a/LeetCode/431-440/433. &#26368;&#23567;&#22522;&#22240;&#21464;&#21270;&#65288;&#20013;&#31561;&#65289;.md b/LeetCode/431-440/433. &#26368;&#23567;&#22522;&#22240;&#21464;&#21270;&#65288;&#20013;&#31561;&#65289;.md
@@ -109,30 +109,27 @@ class Solution {
 &#20195;&#30721;&#65306;
 ```Java
 class Solution {
-    String S, T;
+    static char[] items = new char[]{'A', 'C', 'G', 'T'};
     Set<String> set = new HashSet<>();
-    static char[] items = new char[]{'A','C','G','T'};
-    public int minMutation(String _s, String _e, String[] bank) {
-        S = _s; T = _e;
+    public int minMutation(String S, String T, String[] bank) {
+        set.add(S);
         for (String s : bank) set.add(s);
-        return bfs();
-    }
-    int bfs() {
+        if (!set.contains(T)) return -1;
         Deque<String> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>();
+        d1.addLast(S); d2.addLast(T);
         Map<String, Integer> m1 = new HashMap<>(), m2 = new HashMap<>();
-        d1.addLast(S); m1.put(S, 0);
-        d2.addLast(T); m2.put(T, 0);
+        m1.put(S, 0); m2.put(T, 0);
         while (!d1.isEmpty() && !d2.isEmpty()) {
             int t = -1;
-            if (d1.size() <= d2.size()) t = update(d1, m1, m2);    
+            if (d1.size() <= d2.size()) t = update(d1, m1, m2);
             else t = update(d2, m2, m1);
             if (t != -1) return t;
         }
         return -1;
     }
     int update(Deque<String> d, Map<String, Integer> cur, Map<String, Integer> other) {
-        int size = d.size();
-        while (size-- > 0) {
+        int m = d.size();
+        while (m-- > 0) {
             String s = d.pollFirst();
             char[] cs = s.toCharArray();
             int step = cur.get(s);
@@ -142,12 +139,10 @@ class Solution {
                     char[] clone = cs.clone();
                     clone[i] = c;
                     String sub = String.valueOf(clone);
-                    if (!set.contains(sub)) continue;
-                    if (other.containsKey(sub)) return step + 1 + other.get(sub);
-                    if (!cur.containsKey(sub) || cur.get(sub) > step + 1) {
-                        cur.put(sub, step + 1);
-                        d.addLast(sub);
-                    }
+                    if (!set.contains(sub) || cur.containsKey(sub)) continue;
+                    if (other.containsKey(sub)) return other.get(sub) + step + 1;
+                    d.addLast(sub);
+                    cur.put(sub, step + 1);
                 }
             }
         }
