Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // LeetCode URL: https://leetcode.com/problems/rotate-string/
- /**
- * All rotations of A are contained in A+A
- *
- * Time Complexity: O(N^2)
- *
- * Space Complexity: O(N)
- *
- * N = Length of input string A or B
- */
- class Solution1 {
- public boolean rotateString(String A, String B) {
- if (A == null || B == null || A.length() != B.length()) {
- return false;
- }
- return (A + A).contains(B);
- }
- }
- /**
- * All rotations of A are contained in A+A. Using KMP for checking contains.
- *
- * Time Complexity: O(N)
- *
- * Space Complexity: O(N)
- *
- * N = Length of input string A or B
- */
- class Solution {
- public boolean rotateString(String A, String B) {
- if (A == null || B == null || A.length() != B.length()) {
- return false;
- }
- if (A.length() == 0) {
- return true;
- }
- int[] lookupTable = genLookupTable(B);
- return contains(A + A, B, lookupTable);
- }
- private int[] genLookupTable(String s) {
- int[] table = new int[s.length()];
- int i = 1;
- int index = 0;
- while (i < s.length()) {
- if (s.charAt(i) == s.charAt(index)) {
- index++;
- table[i] = index;
- i++;
- } else {
- if (index > 0) {
- index = table[index - 1];
- } else {
- i++;
- }
- }
- }
- return table;
- }
- private boolean contains(String haystack, String needle, int[] lookupTable) {
- int i = 0;
- int j = 0;
- while (i < haystack.length() && j < needle.length()) {
- if (haystack.charAt(i) == needle.charAt(j)) {
- i++;
- j++;
- } else {
- if (j > 0) {
- j = lookupTable[j - 1];
- } else {
- i++;
- }
- }
- }
- if (j == needle.length()) {
- return true;
- } else {
- return false;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement