Java solution, Memorized BFS


  • 4

    General idea is Memorized BFS. Some optimization to reduce status to be searched.

    1. Use a class Stat to describe a status which contains two fields: currLen stands for the length of current A(s), clipLen stands for the length of A(s) in clipboard.
    2. For each Stat, there's two possible moves: Copy All and Paste. But we can trim some of them using following methods.
    3. If we see a Stat second time, no need to continue (by using a String HashSet);
    4. If new length is greater than target length, no need to do Paste.
    public class Solution {
        class Stat {
            int currLen;
            int clipLen;
            public Stat (int a, int b) {
                currLen = a; clipLen = b;
            }
        }
        
        public int minSteps(int n) {
            if (n == 1) return 0;
            
            int step = 1;
            Queue<Stat> queue = new LinkedList<>();
            queue.add(new Stat(1, 1));
            Set<String> set = new HashSet<>();
            set.add("1,1");
            
            while (!queue.isEmpty()) {
                step++;
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    Stat s = queue.poll();
                    // Copy All
                    if (!set.contains(s.currLen + "," + s.currLen)) {
                        queue.add(new Stat(s.currLen, s.currLen));
                        set.add(s.currLen + "," + s.currLen);
                    }
                    // Paste
                    if (s.currLen + s.clipLen == n) return step;
                    if (!set.contains((s.currLen + s.clipLen) + "," + s.clipLen) && s.currLen + s.clipLen < n) {
                        queue.add(new Stat(s.currLen + s.clipLen, s.clipLen));
                        set.add((s.currLen + s.clipLen) + "," + s.clipLen);
                    }
                }
            }
            
            return -1;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.