AC Without Recursion, O(n) Solution. Really correct?


  • 0
    B

    Iterate from two directions (0 to end& end to 0).
    It gets accepted but I guess there is some uncovered cases.

    public class Solution {
        public boolean wordBreak(String s, Set<String> dict) {
            int index = 0 ;
            int i = 0;
            boolean flag = true;
            while (flag){
            	flag=false;
            	for(i=s.length()-index;i>0;i--){
            		if(dict.contains(s.substring(index, index+i))) 
            			{
            			index=index+i;//right
            			if(index==s.length()) return true;
            			flag=true;
            			break;
            			}
            	}
            	
            }
            flag = true;
           index = 0;
           while (flag){
        	   flag=false;
            	for(i=0;i<=s.length()-index;i++){
            		if(dict.contains(s.substring(index, index+i))) 
            			{
            			index=index+i;
            			if(index==s.length()) return true;
            			flag=true;
            			break;
            			}
            	}
            	
            }       
    		return false;
             
      }
    }

  • 2
    C

    uncovered case,for example:
    "abcdef"
    ["ab","abc","abcd","def"]


Log in to reply
 

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