comparison question BFS


  • 0
    S

    why does traversing the list for each word and checking if it differ by 1 character much slower
    than changing the character in each string 26 times? Does it depend on the problem's restriction?
    say if the length of each word is like 100000 and the list size is only 1000?

    so is it roughly NNM vs N*M^26?

    Say that the word length is M and the list size is N

    Traversing list:
    Running time for each string goes through each list, running time, for each word loop through all the list and check if it differ by 1 -> NN M

    public class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Queue <String> myQueue = new LinkedList<String>();
    Set <String> visited = new HashSet<String>();
    myQueue.add(beginWord);
    visited.add(beginWord);
    int layers = 1;
    int nextLayerCount = 0;
    int currentLayerCount = 1;
    boolean found = false;
    while(!myQueue.isEmpty()){
    String s= myQueue.poll();
    currentLayerCount--;
    if(s.equals(endWord)){
    return layers;
    }

    		for(int i = 0 ; i < wordList.size() ; i++){
    		    String strs= wordList.get(i);
    			if(!visited.contains(strs)){
    				if(transformable(s, strs)){
    					myQueue.add(strs);
    					visited.add(strs);
    					nextLayerCount++;
    				}    				
    			}    			
    		}   
    		if(currentLayerCount == 0){
                currentLayerCount = nextLayerCount;   
                nextLayerCount = 0;
                layers++;
    		}
    
    	}    	
        return 0;
    }
    public boolean transformable(String a, String b){
    	int count = 0;
    	if(a.length() != b.length()) return false;
    	for(int i = 0 ; i< a.length() ; i++){
    		if(a.charAt(i) != b.charAt(i)){
    			count++;
    		}    		
    		if(count > 1) return false;
    	}
    	if(count > 1) return false;
    	else return true;    	
    }
    

    }

    Code taken from Sheva's solution:
    For each string (M) transform 26 times(26) and check if it is contained by the list
    N*M^26?

    public class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> set = new HashSet<>();
    for (String s : wordList) {
    set.add(s);
    }
    if (!set.contains(endWord)) return 0;
    Queue<String> queue = new LinkedList<>();
    queue.offer(beginWord);
    int step = 1;
    while (!queue.isEmpty()) {
    int size = queue.size();
    for (int i = 0; i < size; i++) {
    String s = queue.poll();
    char[] arr = s.toCharArray();
    for (int j = 0; j < arr.length; j++) {
    char original = arr[j];
    for (char c = 'a'; c <= 'z'; c++) {
    if (c == arr[j]) continue;
    arr[j] = c;
    String test = String.valueOf(arr);
    if (test.equals(endWord)) return step + 1;
    if (set.contains(test)) {
    queue.offer(test);
    set.remove(test);
    }
    }
    arr[j] = original;
    }
    }
    step++;
    }
    return 0;
    }
    }


Log in to reply
 

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