DFS java


  • 1
    S
    class Solution {
        // check
        // if two seqs only diff in one char it is a valid mutation
        // find all the seq has one diff
        // get closer to the end.
        // keep a explored Set
        
        
            
        public int minMutation(String start, String end, String[] bank) {
            boolean[] explored = new boolean[bank.length];    
            if (bank.length == 0) return -1;
            return minMutation(explored, start, end,  bank);
            
        }
        
        int minMutation(boolean[] explored, String start, String end, String[] bank) {
            
            if (start.equals(end)) return 0;
            
            int step = bank.length + 1;
            for (int i = 0; i < bank.length; i++) {
                if (diffOne(start , bank[i]) && ! explored[i]) {
                    explored[i] = true;
                    int temp = minMutation(explored, bank[i], end, bank);
                    if (temp != -1) {
                        step = Math.min(step, temp);    
                    }                
                    explored[i] = false;
                }                        
            }
            return step == bank.length + 1 ? -1 : 1 + step;
        }
        
        
        boolean diffOne(String s1, String s2) {
            char[] s1c = s1.toCharArray();
            char[] s2c = s2.toCharArray();
            int count = 0;
            for (int i = 0; i < s1c.length; i++) {
                if (s1c[i] != s2c[i]) count ++;
                if (count >= 2) return false;
            }
            return count == 1;
        }
    }
    

  • 0
    public int minMutation(String start, String end, String[] bank) {
         recurse(start, end, bank, 0, new HashSet<String>());
        return count == Integer.MAX_VALUE ? -1 : count;
    }
    int count = Integer.MAX_VALUE;
    private void recurse(String start, String end, String[] bank, int soFar, Set<String> visited) {
        if(start.intern() == end.intern()) {
            count = Math.min(count, soFar);
        }
        
        for(String e : bank) {
            int diff = 0;
            for(int i = 0; i < e.length(); i++) {
                if(start.charAt(i) != e.charAt(i)) {
                    diff++;
                    if(diff > 1) break;
                }
            }
            if(diff == 1 && !visited.contains(e)) {
                visited.add(e);
                recurse(e, end, bank, soFar+1, visited);
                visited.remove(e);
            }
        }
    }

  • 0
    G

    Why the C++ version cannot pass the OJ, it's exactly the same as your Java version?

    class Solution {
    public:
    	int minMutation(string start, string end, vector<string>& bank) {
    		vector<bool> explored(bank.size(), false);
    		if (bank.empty()) return -1;
    		return minMutation(explored, start, end,  bank);
    	}
    	bool minMutation(vector<bool>& explored , string start, string end, vector<string>& bank) {
    		if (start == end) return 0;
    		int step = bank.size() + 1;
    		for (int i = 0; i < bank.size(); ++i) {
    			if (diffOne(start, bank[i]) && explored[i]) {
    				explored[i] = true;
    				int temp = minMutation(explored, bank[i], end, bank);
    				if (temp != -1) {
    					step = min(step, temp);
    				}
    				explored[i] = false;
    			}
    		}
    		return step == bank.size() + 1 ? -1 : 1 + step;
    	}
    	bool diffOne(string& s1, string& s2) {
    		int count = 0;
    		for (int i = 0; i < s1.size(); ++i) {
    			if (s1[i] != s2[i]) ++count;
    			if (count >= 2) return false;
    		}
    		return count == 1;
    	}
    };

Log in to reply
 

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