Java Solution - Just keep building (OJ Missing Test Cases)


  • 18

    Since LC has so many test cases missing, I wrote new code.
    The idea is to keep string builder and appending until the length A is greater or equal to B.

     public int repeatedStringMatch(String A, String B) {
    
        int count = 0;
        StringBuilder sb = new StringBuilder();
        while (sb.length() < B.length()) {
            sb.append(A);
            count++;
        }
        if(sb.toString().contains(B)) return count;
        if(sb.append(A).toString().contains(B)) return ++count;
        return -1;
    }
    

    Here's the old idea I used which got accepted with multiple bugs.

    Idea is to count all A in B as first step.
    Then remove all A in B.
    Then remaining B is either present in A or A+A.

    public int repeatedStringMatch(String A, String B) {
        int i = 0, count = 0;
        while (i < B.length()) {
            int idx = B.indexOf(A, i);
            if (idx == -1) break;
            i = idx + A.length();
            count++;
        }
        B = B.replaceAll(A, ""); // remaining B if valid, should be smaller than A
        if (!B.isEmpty()) {
            if (A.startsWith(B)) count++; // B is substring AND first part of A
            else if(A.contains(B)) return -1; // B is substring somewhere in between
            else if ((A + A).contains(B)) count += 2; // B in rotating A
            else return -1;
        }
        return count;
    }

  • 0
    S

    I think this solution would fail with test case:
    A= "abcd"
    B="abcdb"

    should return -1, but this solution returns 3, because after B=B.replaceAll(A, ""),
    B would be "b", and A.cotnas(B) is true, then the solution would exectue count++ and return count;

    @wavy said in Java Solution - String Replacement:

    public int repeatedStringMatch(String A, String B) {

    int i = 0, count = 0;
    while (i < B.length()) {
        int idx = B.indexOf(A, i);
        if (idx == -1) break;
        i = idx + A.length();
        count++;
    }
    B = B.replaceAll(A, "");
    if (!B.isEmpty()) {
        if (A.contains(B)) count++;
        else if ((A + A).contains(B)) count += 2;
        else return -1;
    }
    return count;
    

    }


  • 0

    @SharonSu said in Java Solution - String Replacement:

    I think this solution would fail with test case:

    Wow! Thank you so much. I think OJ miss this test case.
    I updated with the fix.


  • 0
    P

    I still think your solution will fail
    A = "abc"
    B = "aabcbabcc"
    Answer should be -1, but your solution will return 3.
    after B=B.replaceAll(A, ""), B = "abc"
    and A.startsWith(B), so it will increase count.


  • 0

    @prashantbhar said in Java Solution - String Replacement:

    I still think your solution will fail

    Brilliant counter example! Leetcode miss so many test case it's unfortunate.
    I've updated with new code.


  • 0
    P
    This post is deleted!

  • 0

    @wavy Some new test cases were added, thanks.


  • 0
    H

    Actually, many results in the contests are wrong !


  • 0

    @wavy: Thank you for your solution. If I understand correctly, you do sb.append(A).toString().contains(B), to handle the case of rotation, correct?


  • 0

    @BatCoder That's correct


  • 0
    N

    @wavy
    Thanks for your idea. I rewrote your code:

    class Solution {
        public int repeatedStringMatch(String A, String B) {
            for (String C = A; C.length() < B.length() + A.length()*2; C += A) 
                if (C.contains(B)) return C.length()/A.length();
            return -1;
        }
    }
    

    And in this thread I tried to explain why the stop condition is : C.length() >= 2*A.length() + B.length() .
    It may help to understand why your algorithm be correct.

    With a second thought, I decreased the time to repeat C with A from O(N) to O(lgN):

    class Solution {
        public int repeatedStringMatch(String A, String B) {
            String C = A, P = A;
            int n = (B.length()+A.length()-1) / A.length();    //n = ceil(len(B)/len(A))
            for (int i = n; i > 0; i/=2, P+=P) 
                if (i % 2 == 1) C += P;                        //C = A * power(A, n)
            int j = C.indexOf(B);                                         //where does B start in C?
            return j < 0 ? -1 : (j+B.length() <= n*A.length()) ? n : n+1; //where does B end   in C?
        }
    }
    

    n = ceil(len(B) / len(A)) is also explained in that thread.


  • 0
    N

    @awice
    Please review this case:

    A = "abcd"
    B = "cdabcdab"
    

    The incorrect answer below is still AC now:

        public int repeatedStringMatch(String A, String B) {//AC with a WRONG case: A=abcd, B=cdabcdab
            for (String C = new String(A); C.length() <= Math.max(A.length(), B.length()) + A.length(); C += A) 
                if (C.contains(B)) return C.length()/A.length();
            return -1;
        }
    

  • 0
    S

    @wavy

    sb.toString().contains(B) will cause the program to exceed the time limit for the following case:

    A --> "aaaaa....aaaaa" (49999 a's)
    B --> "aaaaa....aaaaab" (49999 a's 1 b)


  • 0
    S

    @smttsp apparently, the max length of a string is 10000. So your code still works fine!


Log in to reply
 

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