What is the big-O of my codes?
helloworld2046
62

Hi I am having troubles to figure out big-O.
Can you help me?
I have two pieces of code. Their purposes are the same but the top one is without visited[] and the bottom one is with visited[]

  • With visited[]
public boolean wordBreak(String s, List<String> wordDict){
	Set<String> wordDictSet = new HashSet<>(wordDict);
	Queue<Integer> queue = new LinkedList<>();
	boolean[] visited = new boolean[s.length()];
	queue.add(0);
	while(!queue.isEmpty()){
		int start = queue.remove();
		for(visited[start] == false){
			for(int end = start + 1; end <= s.length(); end++){
				if(wordDictSet.contains(s.substring(start, end)){
					queue.add(end);
					if(end == s.length()){
						return true;
					}
				}
			}
		}
		visited[start] = true;
	}
	return false;
}
  • Without visited[]
public boolean wordBreak(String s, List<String> wordDict){
	Set<String> wordDictSet = new HashSet<>(wordDict);
	Queue<Integer> queue = new LinkedList<>();
	queue.add(0);
	while(!queue.isEmpty()){
		int start = queue.remove();
		for(int end = start + 1; end <= s.length(); end++){
			if(wordDictSet.contains(s.substring(start, end)){
				queue.add(end);
				if(end == s.length()){
					return true;
				}
			}
		}
	}
	return false;
}
Comments (3)