Java O(n) time, O(1) space efficient solution. Beat 99%.


  • 0
    X
    
             public int repeatedStringMatch(String A, String B) {
    		int count = 1;
                    int i = 0;
    		for (int j = 0; j < B.length(); j++) {
    	           if (A.charAt(i) != B.charAt(j)) {
                          if (count > 1) {       // already second time: no way to make B from A
                             return -1;
                          }
                          j = -1;    // try to match j's starting character with next i
    		   }
                
                       i++;
    		   if (i == A.length()) {        // one more time of A
                          if (j == B.length() - 1) {
                             break;
                          } 
    		      count++;
    		      i = 0;
    		   }
    		}
    		return count;
    	   }
    
    

  • 0
    Z

    Hi, your solution is amazingly fast. Yet I can not understand well. Could you please add more comment in your code?


  • 0
    X

    @zainyu717 I tried matching the first letter in B with a letter in A. Then I could be able to scan B to get the count by updating i and j simultaneously.


  • 1
    J

    This is just another fast solution that fails a simple case.
    A: "aaac", B: "aac"


  • 0

    @xavierliu Can you explain your logic?
    A: "aaac", B: "aac" did return -1 and it is wrong:(


  • 0
    J

    @tongzhou2 The solution here tries to match a suffix of A and prefix of B. No need to repeat A if it fails. Otherwise, repeat A and keep on matching.
    However, the match of A suffix and B prefix reduces to the string matching problem which is implemented incorrectly here.
    This can be illustrated as below.
    aaac---aac
    aaac---aac
    aaac---aac // not a match
    aaac---aac // incorrect here


Log in to reply
 

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