what is the time and space complexity if i use single BFS for this problem?


  • 0
    O

    what is the time and space complexity if i use single BFS for this problem?
    similar to this one
    https://discuss.leetcode.com/topic/36771/java-accepted-bfs
    thanks

    public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
    Queue<String> q = new LinkedList<>();
    q.add(beginWord);
    wordList.remove(beginWord);
    int level = 1;
    while(!q.isEmpty()){
    int size = q.size();
    for(int i = 0; i < size; i++){
    String s = q.remove();
    for(int j = 0; j < s.length(); j++){
    for(char c = 'a'; c <= 'z'; c++){
    char[] cc = s.toCharArray();//start from the original string
    cc[j] = c;
    String next = new String(cc);
    if(next.equals(endWord)){
    return level + 1;
    }else if(wordList.contains(next)){
    q.add(next);
    wordList.remove(next);
    }
    }
    }
    }
    level++;
    }
    return 0;
    }
    }>! >! Spoiler


Log in to reply
 

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