public static boolean isRotation(String s1, String s2)
{
int len = s1.length();
// check that s1 and s2 are equal length and not empty
if ( len == s2.length() && len > 0 )
{
/* concatenate s1 and s1 within new buffer */
String s1s1 = s1 + s1;
return isSubstring(s1s1,s2);
}
return false;
}
3. Similar Ones
public static void setZeroes(int[][] matrix)
{
// validate the input
if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
return matrix;
boolean rowFlag = false;
boolean colFlag = false;
// check 1st row
for (int j=0 ; j < matrix[0].length; j++)
{
if ( matrix[0][j] == 0)
{
rowFlag = true;
// NOTE: break
break;
}
}
// check 1st column
for(int i =0 ; i < matrix.length; i++)
{
if (matrix[i][0] == 0)
{
colFlag = true;
// NOTE: break
break;
}
}
// move the rest to the first column and row
//for (int i = 0 ; i < matrix.length; i++)
// NOTE: already check 1st col
for ( int i =1 ; i < matrix.length ; i++)
{
//for (int j = 0 ; j < matrix[0].length; j++)
for (int j = 1; j < matrix[0].length; j++)
{
if (matrix[i][j] == 0 )
{
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
// set Zeroes
for (int i = 0 ; i < matrix.length; i++)
{
for (int j= 0; j < matrix[0].length;j++)
{
if ( matrix[i][0] == 0 || matrix[0][j] == 0)
matrix[i][j] = 0;
}
}
if (rowFlag)
{
for (int j = 0; j < matrix[0].length ; j++)
matrix[0][j] = 0;
}
if (colFlag)
{
for (int i = 0 ; i < matrix.length; i++)
matrix[i][0] = 0;
}
}
3. Similar ones
public void rotate(int[][] matrix, int n)
{
// vlaidate the input
if ( matrix == null || matrix.length ==0 || matrix[0].length == 0)
{
return matrix;
}
//
for ( int i = 0 ; i < n/2 ; i++)
{
for ( int j = i ; j < n -1 ; j++ )
{
int tmp = matrix[i][j];//top
matrix[i][j] = matrix[n-1-j][i];//top<-left
matrix[n-1-j][i] = matrix[n-1-i][n-1-j];//left<-bottom
matrix[n-1-i][n-1-j] = matrix[j][n-1-i];//bottom<-right
matrix[j][n-1-i] = tmp;// right<-top
}
}
}
3. Similar Ones
// Assume the length of char[] is enough to hold
// all replaced string
public static void replaceSpace(char[] str, int length)
{
int spaceCount = 0; newLength, i = 0;
for (i = 0; i < length; i++)
{
if (str[i] == ' ')
spaceCount++;
}
// I am so
// o
// o\0
// s
//
// so\0
// ' '
// %20so\0
newLength = length + spaceCount*2;
str[newLength] = '\0';
for ( int i= length-1; i >= 0; i-- )
{
if ( str[i] == ' ' )
{
str[newLength -1] = '0';
str[newLength -2] = '2';
str[newLength -3] = '%';
newLength = newLength -3;
}
else
{
str[newLength-1] = str[i];
newLength = newLength -1;
}
}
}
3. Similar Ones
// Time:O(n log n), Space:O(n) for sorting
public static boolean anagram(String s , String t)
{
//validate the input
if (s.length() != t.length())
return false;
String sortedS = new String(Arrays.sort(s.toCharArray()));
String sortedT = new String(Arrays.sort(t.toCharArray()));
return sortedS == sortedT;
}
// NOTE: In order not to check all letters[256] to see if any on
// of it is not Zero. Use num_unique_chars and num_completed_t
public static boolean anagram(String s, String t)
{
// validate the input
if ( s.length() != t.length() )
return false;
int[] letters = new int[256];
int num_unique_chars = 0;
int num_completed_t = 0;
char[] s_array = s.toCharArray();
for (char c: s_array)
{
if(letters[c]==0) ++num_unique_chars;
++letters[c];
}
for (int i = 0; i < t.length(); i++)
{
int c = (int) t.charAt(i);
if ( letters[c] == 0 )
return false;
--letters[c];
if ( letter[c] == 0)
{
++num_completed_T;
// NOTE: completed == unique AND is last character
if ( num_completed_t == num_unique_chars )
{
// it's a match if t has been processed completely
return i == t.length() -1;
}
}
}
return false;
}
// Time :O(n^2) , Space:O(1)
// Keep a new Index with all unique characters, and every incoming
// character need to check with them
public static void removeDuplicate( char[] str)
{
//validate the input
if ( str == null )
return;
int len = str.length;
if ( len < 2 )
return;
int tail =1;
for (int i =1; i < len; ++i)
{
int j;
// NOTE: compare with new string with all unique characters
for (j = 0 ; j < tail; ++j)
{
if ( str[i] == str[j] )
break;
}
// NOTE: it is a unique one
if ( j == tail )
{
str[tail] = str[i];
++tail;
}
}
// NOTE: last null character
str[tail] = 0;
}
// Time :O(n), Space:O(1)[256]
// Assume all ASCII characters
public static void removeDuplicate(char[] str)
{
// validate the input
if (str == null)
return;
int len = str.length;
if (len < 2)
return;
boolean[] hit = new boolean[256];
for (int i = 0 ; i < 256; ++i)
{
hit[i] = false;
}
hit[str[0]] = true;
int tail = 1;
for (int i =1; i < len; ++i)
{
if ( !hit[str[i]] )
{
str[tail] = str[i];
++tail;
hit[str[i]] = true;
}
}
str[tail] = 0;
}
3. Similar onesvoid reverse (char *str)
{
char *end = str; // a new pointer point to str
char tmp;
if ( str )
{
// 1. Get the right most char
while (*end)
++end;
--end; // back one char from last '0' char
// 2. Get the left most char , str It is
// 3. Start Swapping
while ( str < end )
{
tmp = *str; // left most to tmp
*str++ = *end; // left most and right most SWAP and left most ++
*end-- = tmp; // right most assign and right most --
}
}
}
3. Similar Ones
//1. Time :O(n), n is the length of the string, Space:O(n), [256]
// NOTE: assume char set is ASCII
public static boolean isUniqueChars(String str)
{
//validate the input
if (str == null)
return true;
boolean[] char_set = new boolean[256];
for ( int i = 0 ; i < str.length(); i++ )
{
int val = str.charAt(i);
if ( char_set[val] )
return false;
char_set[val] = true;
}
return true;
}
//2. Time:O(n) , Space:O(1), int checker 32 bit
// reduce our space usage by using bit vector
// NOTE: int 32 bit but assume only 'a'-'z', we only need 26 bit
// 'a'-> bit 0
// 'z'-> bit 25
public static boolean isUniqueChars(String str){
int checker = 0;
for (int i = 0; i < str.length(); i++)
{
int val = str.charAt(i) - 'a';
// NOTE : Test bit
if ( ( checker & (1<0 )
{
return false;
}
// NOTE : Set bit
checker |= (1<
//3. Time :O(n^2), Space:O(1)
// Two nested for loop
// check every char of the string with every other char of the string
// for duplicate occurRences
//4. Time :O(n log n) time, Space:O(n), sorting algorithm
// mergeO(n),heapO(1),quickO(n)
// linearly check the string for neighboring characters that are
// identical.
// Careful, though - many sorting algorithms take up extra space
3. Similar Ones