Easy to understand JAVA solution with implementation idea.


  • 0
    A

    The idea is -

    1. Find all the factors of the length of the string.
    2. Form a string equal to length of the original string by appending substrings(of length = each factor) of the original string.
    3. Compare if the original string and string formed in Step 2 are equal or not. If yes, return TRUE. Else, continue forming strings with the next factor(Step 2).
    public boolean repeatedSubstringPattern(String str) {
            if(str.length()==1) return false;
            List<Integer> factors = new ArrayList<>();
            factors.add(1);
            for(int i=2;i<str.length();i++)
            {
                if(str.length()%i==0)
                    factors.add(i);
            }
            for (int factor: factors)
            {
                String sub = str.substring(0,factor);
                StringBuilder sb = new StringBuilder();
                while(sb.length()<str.length())
                {
                    sb.append(sub);
                }
                if(str.equals(sb.toString()))
                {
                    return true;
                }
            }
            return false;
    }
    
    

    I had tried an alternative approach to this problem initially. However, only one test case failed using that approach. It would be of great help if someone can point out a way to handle the test case "abcabcabc" using the below approach. Thanks for your help. :)

    public boolean repeatedSubstringPattern(String str) {
    		       if(str=="") return true;
    		       if(str.length()==1) return false;
    		      /*For handling strings formed by repeating single character*/
                           char ch = str.charAt(0);
    		       int i;
    		       for( i=0;i<str.length();i++)
    		       {
    		           if(str.charAt(i)!=ch)
    		                break;
    		       }
    		       if(i==str.length())return true;
     /* For rest of the strings, the basic idea is : Divide the string and check whether both the halves are equal or not. If they are not equal, then definitely their inner(recursive) halves won't be repeating substrings. */ 
    		       String str1 = str.substring(0,((str.length()-1)/2)+1);
    		       String str2;
    		       str2 = str.substring(((str.length()-1)/2)+1);
    		return (str1).equals(str2); 
    }
    
    

Log in to reply
 

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