3ms C++ O(n) solution


  • -1
    class Solution {
    public:
        int repeatedStringMatch(string A, string B) {
            int i = 0, j = 0, count = 1;
            while(j < B.size()){
                while(i < A.size() && A[i] != B[j]) i++;
                if(i == A.size() || count > 1) return -1;
                while(j < B.size() && A[i++] == B[j++]){
                    if(j == B.size()) return count;
                    if(i == A.size()) i = 0, count++;
                }
                j = 0;
            }
        }
    };
    

    Update:

    class Solution {
    public:
        int repeatedStringMatch(string A, string B) {
            if(B.empty()) return 1;
            for(int i = 0, j = 0; j < B.size() && i < A.size(); i++, j = 0){
                while(i < A.size() && A[i] != B[j]) i++;
                int k = i, count = 1;
                while(A[k++] == B[j++]){
                    if(j == B.size()) return count;
                    if(k == A.size()) k = 0, count++;
                }
            }
            return -1;
        }
    };
    

  • 0
    J

    failed at
    A = "aaab"
    B = "aab"

    @administrators @contributors
    we should add this test case into OJ

    @zefengsong said in 3ms C++ O(n) solution:

    class Solution {
    public:
    int repeatedStringMatch(string A, string B) {
    int i = 0, j = 0, count = 1;
    while(j < B.size()){
    while(i < A.size() && A[i] != B[j]) i++;
    if(i == A.size() || count > 1) return -1;
    while(j < B.size() && A[i++] == B[j++]){
    if(j == B.size()) return count;
    if(i == A.size()) i = 0, count++;
    }
    j = 0;
    }
    }
    };


  • 0

    @jordandong You are right, thx for pointing out. How about the updated one?


Log in to reply
 

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