word break - Java - mock interview - BFS algorithm

wordBreak.Java

/*
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
             Note that you are allowed to reuse a dictionary word.
Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false
 */

/*
  Input: 
  Input: s = "leetcode", wordDict = ["leet", "code"]
              x. 3
              
  s = "applepenapple", wordDict = ["apple", "pen"]
      apple pen apple
      
  Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
                          SET
    cat -> sand -> og X
    cats -> and -> og X
    
  false
  
  "catsandog"
   01234567
   
   0 -> 3 -> 4 -> 6
   
   S: O(N)
   T: O(N) * O(N/2)
   With memo: O(N)
   s = "zzzzzz", w: z, zzzz
   
   Approach:
   VisitedIndex: O(N)
   
   BFS with start indexes
   
   0 -> 3 -> 4 -> 6 -> 6
   
   I am not able to hear your clearly
   
  catsandog
  012345678
  
  wordDict = ["cats", "dog", "sand", "and", "cat"]
  
  BFS Queue => have index
  0 -> 3 -> 4 -> 7 -> 7 -> 9
  
  c
  ca
  cat
  cats
  catsandog
  
  sandog
  
  andog
  
  og
  
  o
  
  return false
  */

    
  public boolean wordBreak(String s, List<String> wordDict) {
    
    Set<String> dict = new HashSet<>(wordDict);
    
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(0);
    
    Set<Integer> visited = new HashSet<>();
    
    while(!queue.isEmpty()) {
      int start = queue.poll();
      if(start == s.length()) {
        return true;
      }
      
      if(visited.contains(start)) {
        continue;
      }
      
      visited.add(start);
      
      for(int end = start; end < s.length(); end++) {
        if(dict.contains(s.substring(start, end))) {
          queue.offer(end+1);
        }
      }
    }
    
    return false;
  }