Find if a String is rotation of another String – Java Implementation

This is a simple yet popular Java interview question. Given two Strings how can you tell if they are rotations of each other? For example, the word “bottle” and “ottleb” or “ttlebo” are rotations of each other. Start thinking as writing this word in a tire uniformly and reading it from any character.

The solution is simple, if you know how to do it. If you take the first word and concatenate it with itself, any rotating string should be sub-string of such a concatenated word. And there you go !

The following is a java implementation of this simple algorithm. I have also provided a little advance solution by setting the case sensitivity flag to true or false.

package com.icodejava.blog.published;
/**
 * 
 * @author Kushal Paudyal
 * Created on: 1/9/2017
 * Last Modified on: 1/9/2017
 *
 */
public class StringRotationFinder {
	private static final boolean CASE_SENSITIVE = true;
	public static void main (String args []) {
		String firstString = "This is a beautiful house";
		String secondString ="a beautiful housethis is ";
		
		isRotated(firstString, secondString, CASE_SENSITIVE);
		isRotated(firstString, secondString, !CASE_SENSITIVE);
		
	}

	/**
	 * The rotated string is a subset of non-repeated String + non-repeated String
	 * 
	 * e.g. "abc abd" is original string and "c abda" which is a part of "abc abdabc abd"
	 * 
	 * This method uses a case sensitivity flag.
	 */
	private static void isRotated(String firstString, String secondString, boolean isCaseSensitive) {
		System.out.println("First String: " + firstString);
		System.out.println("Second String: " + secondString);
		boolean isRotated = false;
		if (firstString != null && secondString != null && firstString.length() == secondString.length()) {
			
			String concatenatedString = firstString + firstString;
			
			//Assuming the cases are not sensitive
			if(!isCaseSensitive) {
				concatenatedString = concatenatedString.toLowerCase();
				secondString = secondString.toLowerCase();
			}
			
			if (concatenatedString.contains(secondString)) {
				isRotated = true;
			}
		}
		
			
		System.out.println("First String and Second Strings are roated forms of is other (Case Sensitive: " +  isCaseSensitive +")? "  + isRotated );
		
	}

}

Here is the output of this program:

First String: This is a beautiful house
Second String: a beautiful housethis is 
First String and Second Strings are roated forms of is other (Case Sensitive: true)? false
First String: This is a beautiful house
Second String: a beautiful housethis is 
First String and Second Strings are roated forms of is other (Case Sensitive: false)? true

In Place Matrix (2D Array) Clockwise and Counterclockwise Rotation – Java Implementation

Below, you will find a java implementation of class that does a matrix or 2 dimensional array rotation both clockwise and anti clockwise. The approach used here does not take extra buffer i.e. does the stuff IN-PLACE. There is another article in this blog where I have implemented this using extra buffer space.

package com.icodejava.blog.published.maths;

import java.util.Arrays;

/**
 * 
 * @author Kushal Paudyal 
 * Created on: 01/05/2017 
 * Last Modified on: 01/05/2017
 *
 * This class demonstrates how to rotate a NxN array 90 degrees using no extra buffer.
   e.g. 
     [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19, 20], [21, 22, 23, 24, 25]]
	 
	 should appear as
	 
	 [[5, 10, 15, 20, 25], [4, 9, 14, 19, 24], [3, 8, 13, 18, 23], [2, 7, 12, 17, 22], [1, 6, 11, 16, 21]]
	 for a 90 degrees counter clockwise rotation

	 
	 [[21, 16, 11, 6, 1], [22, 17, 12, 7, 2], [23, 18, 13, 8, 3], [24, 19, 14, 9, 4], [25, 20, 15, 10, 5]]
	 for a 90 degrees clockwise rotation
	 
 */

public class Rotate2DArrayInPlace {
		
public static void main (String args [] ) throws Exception {
		
		Integer [] [] myNxNArray = new Integer [][] {
			{1, 2, 3, 4, 5},
			{6, 7, 8, 9, 10},
			{11, 12, 13, 14, 15},
			{16,17,18,19,20},
			{21,22,23,24,25}
		};
		
		System.out.println("SOURCE ARRAY: \n" + Arrays.deepToString(myNxNArray));
		Integer [][] rotatedInPlace = rotateMatrixInPlaceCounterClockwise(myNxNArray);
		
		System.out.println("ROTATED IN PLACE - 90 degrees COUNTER CLOCKWISE");
		System.out.println(Arrays.deepToString(rotatedInPlace));
		
		//The array referenced in above definition myNxNArray is changed so you will need to redefine
		Integer [] [] myNxNArray1 = new Integer [][] {
			{1, 2, 3, 4, 5},
			{6, 7, 8, 9, 10},
			{11, 12, 13, 14, 15},
			{16,17,18,19,20},
			{21,22,23,24,25}
		};
		
		Integer [][] rotatedInPlaceClockwise = rotateMatrixInPlaceClockwise(myNxNArray1);
		
		System.out.println("ROTATED IN PLACE - 90 degrees CLOCKWISE");
		System.out.println(Arrays.deepToString(rotatedInPlaceClockwise));
		
	}
	
	/**
	 * This method rotates the matrix 90 degrees counter clockwise without using extra buffer..
	 */
	public static Integer[][] rotateMatrixInPlaceCounterClockwise(Integer[][] matrix) throws Exception {
		
		if(matrix.length == 0 || matrix.length != matrix[0].length) {
			throw new Exception ("Invalid Input");
		}

		int n = matrix[0].length;
		int tmp;
		for (int i = 0; i < n / 2; i++) {
			for (int j = i; j < n - i - 1; j++) {
				tmp = matrix[i][j];
				matrix[i][j] = matrix[j][n - i - 1];
				matrix[j][n - i - 1] = matrix[n - i - 1][n - j - 1];
				matrix[n - i - 1][n - j - 1] = matrix[n - j - 1][i];
				matrix[n - j - 1][i] = tmp;
			}

		}
		return matrix;
	}
	
	/**
	 * This method rotates the matrix 90 degrees counter clockwise without using extra buffer..
	 */
	public static Integer[][] rotateMatrixInPlaceClockwise(Integer[][] matrix) throws Exception {
		
		if(matrix.length == 0 || matrix.length != matrix[0].length) {
			throw new Exception ("Invalid Input");
		}

		int n = matrix.length;
		int top;
		for (int i = 0; i < n / 2; i++) {
			
			for (int j = i; j < n - i - 1; j++) {
				
				top = matrix[i][j];
				matrix[i][j] = matrix[n - j - 1][i];
				matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
				matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
				matrix[j] [n - i - 1] = top;
			
			}

		}
		return matrix;
	}

}

OUTPUT:

SOURCE ARRAY: 
[[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19, 20], [21, 22, 23, 24, 25]]
ROTATED IN PLACE - 90 degrees COUNTER CLOCKWISE
[[5, 10, 15, 20, 25], [4, 9, 14, 19, 24], [3, 8, 13, 18, 23], [2, 7, 12, 17, 22], [1, 6, 11, 16, 21]]
ROTATED IN PLACE - 90 degrees CLOCKWISE
[[21, 16, 11, 6, 1], [22, 17, 12, 7, 2], [23, 18, 13, 8, 3], [24, 19, 14, 9, 4], [25, 20, 15, 10, 5]]

Matrix (2D Array) Clockwise and Counterclockwise Rotation with Extra Buffer – Java Implementation

Below, you will find a java implementation of class that does a matrix or 2 dimensional array rotation both clockwise and anti clockwise. The approach used here takes extra buffer. There is another article in this blog where I have implemented this in place i.e. without requiring extra buffer space.

package com.icodejava.blog.published.maths;

import java.util.Arrays;

/**
 * 
 * @author Kushal Paudyal 
 * Created on: 01/05/2017 
 * Last Modified on: 01/05/2017
 *
 * This class demonstrates how to rotate a mxn array 90 degrees using extra buffer
   e.g. 
     1  2  3 4 5
	 6  7  8 9 10
	 11 12 13 14 15
	 
	 should appear as
	 
	 11 6 1
	 12 7 2
	 13 8 3
	 14 9 4
	 15 10 5
	 
	 for a 90 degrees clockwise rotation
	 
	 and 
	 
	 5 10 15
	 4 9 14
	 3 8 13
	 2 7 12
	 1 6 11
	 
	 for a 90 degrees counterclockwise rotation
 */
public class Rotate2DArray {

	public static void main(String args[]) throws Exception {

		// define two dimensional array
		Integer[][] myArray = new Integer[][] { 
				{ 1, 2, 3, 4, 5 }, 
				{ 6, 7, 8, 9, 10 }, 
				{ 11, 12, 13, 14, 15 } 
			};

		System.out.println("SOURCE ARRAY: \n" + Arrays.deepToString(myArray));

		Integer[][] rotated = rotateMatrixClockwise(myArray);

		System.out.println("ROTATED ARRAY 90 degrees clockwise:");
		System.out.println(Arrays.deepToString(rotated));
		
		// define two dimensional array
		Integer[][] myArray1 = new Integer[][] { 
				{ 1, 2, 3, 4, 5 }, 
				{ 6, 7, 8, 9, 10 }, 
				{ 11, 12, 13, 14, 15 } 
			};

		System.out.println("SOURCE ARRAY: \n" + Arrays.deepToString(myArray1));

		Integer[][] rotated1 = rotateMatrixCounterClockwise(myArray1);

		System.out.println("ROTATED ARRAY 90 degrees counter clockwise:");
		System.out.println(Arrays.deepToString(rotated1));

	}

	/**
	 * This method rotates the matrix 90 degrees clockwise by using extra
	 * buffer.
	 */
	public static Integer[][] rotateMatrixClockwise(Integer[][] matrix) {
		Integer[][] rotated = new Integer[matrix[0].length][matrix.length];

		for (int i = 0; i < matrix[0].length; ++i) {
			for (int j = 0; j < matrix.length; ++j) {

				
				rotated[i][j] = matrix[matrix.length - j - 1][i];
				
			}
		}

		return rotated;
	}
	
	/**
	 * This method rotates the matrix 90 degrees counter clockwise by using extra
	 * buffer.
	 */
	public static Integer[][] rotateMatrixCounterClockwise(Integer[][] matrix) {
		Integer[][] rotated = new Integer[matrix[0].length][matrix.length];

		for (int i = 0; i < matrix[0].length; ++i) {
			for (int j = 0; j < matrix.length; ++j) {
				
				rotated[i][j] = matrix[j][matrix[0].length - i - 1];
			}
		}

		return rotated;
	}

}

OUTPUT:

SOURCE ARRAY: 
[[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15]]
ROTATED ARRAY 90 degrees clockwise:
[[11, 6, 1], [12, 7, 2], [13, 8, 3], [14, 9, 4], [15, 10, 5]]
SOURCE ARRAY: 
[[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15]]
ROTATED ARRAY 90 degrees counter clockwise:
[[5, 10, 15], [4, 9, 14], [3, 8, 13], [2, 7, 12], [1, 6, 11]]