Share a solution using Boyer-Moore, 4ms in c++ with comments


  • -1
    E
    string shortestPalindrome(string s) {
      int n = s.length();
      if (n < 2) return s;
      string rs = s;
      reverse(rs.begin(), rs.end());
      int right[26]{0}, rright[26]{0}; // the last index of every character
      int j, tmp, i = 0;
      for (i = 0; i < n; ++i) {
        right[s[i] - 'a'] = i;
        rright[rs[i] - 'a'] = i;
      }
      i = 0;
      // match s in rs
      while (i < n) {
        for (j = n - 1 - i; j >= 0; --j) {
          if (s[j] != rs[i + j]) {
            // first check the last rs[i + j] in s and move s to right by j - lastpos
            // s:  aaacbaaaa  // s[5] != rs[5] , find the last rs[5] in s which is 3, so move s right by 5 - 3 
            // rs: aaaabcaaa
            tmp = j - right[rs[i + j] - 'a'];
            if (tmp <= 0) { // UPDATE: the previous method is wrong in case "aabababababaababaa" and I changed the 3 lines code below
              // if the lastpos is right to j, find the next s[j] in rs and move s right to the pos
              // s:    aaacbaaaa    // s[4] != rs[2 + 4] and last rs[6] in s is 8, not valid
              // rs: aaaabcaaa      // so find first s[4] in rs after i + j which is the end, so move s[4] right to end
              tmp = i + j + 1;
              while (tmp < n && rs[tmp] != s[j]) tmp++;
              tmp = tmp - i - j;
            }
            if (tmp <= 0) j = n - i - j;
            else j = tmp;
            i += j;
            break;
          }
        }
        if (j < 0) {
          return rs.substr(0, i) + s;
        }
      }
    
      return rs.substr(0, n - 1) + s;
    }
    

    UPDATE: my previous method is wrong in case "aabababababaababaa" which is not included in test cases @1337c0d3r and I changed

    tmp = rright[s[j] - 'a'] - i - j;
    

    to

    tmp = i + j + 1;
    while (tmp < n && rs[tmp] != s[j]) tmp++;
    tmp = tmp - i - j;

  • 1
    S

    This solution is not good. After j becomes small enough,

       tmp = j - right[rs[i + j] - 'a'];
    

    have a high chance to be less than 0, and you have to perform linear search

       if (tmp <= 0) { // UPDATE: the previous method is wrong in case "aabababababaababaa" and I changed the   3 lines code below
    

    then.

    So it's not good to only record the last position in "right". And why not just use a map for "right"?


  • 0
    E

    Yeah you are right, in the worst cases it's nearly O(n^2), and your suggestion can improve a lot which is very good.
    I proposed it because I think maybe Boyer-Moore can do a better job and just offer a few commonplace remarks by way of introduction so that others like you may come up with valuable opinions.

    My previous thought is to use a matrix[n][26] to save every char's first position behind i in the reversed string, and can change the linear search:
    while (tmp < n && rs[tmp] != s[j]) tmp++;
    to O(1).
    But I found it's hard to find a worst case, and just left it simple and easy to understand.
    I do believe it can be improved a lot. Thank you!


  • 0

    @eidolon said in Share a solution using Boyer-Moore, 4ms in c++ with comments:

    my previous method is wrong in case "aabababababaababaa" which is not included in test cases

    Thanks, I have added the test case.


Log in to reply
 

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