AlgoPlan0603

##open the lock
##not finished


class Solution {
    public int openLock(String[] deadends, String target) {
        if (target.equals("0000")){
            return 0;
        }
        String lock = "0000";
        //got a node starts with 0000 
        List<String> deads = new ArrayList();
        for (String s: deadends){
            deads.add(s);
        }
        //got a list of dead ends
        int count = 0;
        List<String> visited = new ArrayList();
        visited.add("0000");
        int result = bfs(target,lock,deads,count,visited);
        if (result ==0){
            return -1;
        }else{
            return result;
        }
        
    }
    public int bfs(String target, String lock,
                   List<String> deads,int count,
                   List<String> visited){
        List<String> children = new ArrayList();
        String temp ="";
        char[] lockchar = lock.toCharArray();
       //find the children of the lock
        for (int k =0; k < 4;k++){
            lockchar[k] = (char) ((lockchar[k]-'0'+1) % 10);
            temp = String.valueOf(lockchar);
            if (!deads.contains(temp) && !visited.contains(temp))
                children.add(temp);
            lockchar[k] = (char) ((lockchar[k]-'0'-1) % 10+ 10);
            temp = String.valueOf(lockchar);
            if (!deads.contains(temp) && !visited.contains(temp))
                children.add(temp);

        }
        // for (String child:children){
        //          System.out.print(child+ " ");
        // }
        
        for (String child : children){
                //if it is not dead end, is it the target
                if (child == target){
                    count++;
                    break;
                }else{
                    //if it is not dead end, it is not the target, keep looking through its children
                    visited.add(child);
                    // System.out.print(" go to "+ child);
                    count =bfs(target, child, deads,count,visited);
                    // System.out.print(" go out from "+ child);
                }
                count++;
        }
        return count;
    }
}


#palindrome number 
##see if a number reads the same reversely

class Solution {
    public boolean isPalindrome(int x) {
        String s = String.valueOf(x);
        int len = s.length();
        if (len %2 ==0){
            for ( int k = 0; k < len/2; k++){
                if (s.charAt(k) !=s.charAt(len-k-1)){
                    return false;
                }
            }
        }else{
            for (int k = 0 ; k < len/2+1;k++){
                if (s.charAt(k) !=s.charAt(len-k-1)){
                    return false;
                }
            }
        }
        return true;
    }
}

#palindrome linked list
##key idea
-use the poll first and last function of linked list

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        LinkedList<ListNode> list = new LinkedList();
        ListNode temp = head;
        while (temp !=null){
            list.add(temp);
            temp = temp.next;
        }
        ListNode front;
        ListNode back;
       while (list.size()>1){
           front = list.pollFirst();
           back = list.pollLast();
           if (front.val !=back.val){
               return false;
           }
       }
        return true;
    }
}