[Interview ]1. Arrays and Strings

Hash Tables

ArrayList & Resizeable Arrays

amortized insertion running time is O(1)

StringBuilder

The time complexity for using "+" to concatenate a string array is O(x + 2x + 3x + ... + nx) = O(xn^2).

String joinWords(String[] words) {
      String sentence = "";
      for (String w : words) {
            sentence = sentence + w;
      }
      return sentence;
}

StringBuidler helps avoid the problem by using a resizable array of all the strings.

Exercise Method

Impelement your own version of StringBuilder, HashTable and ArrayList.

Additional Reading

Hash Table Collision Resolution (pg 636)
Rabin-Karp Substring Search (pg636)

Interview Question

1.1 Is Unique

Implement an algorithm to determine if a string has all unique characters. What if you cannot use an additional data structure?
Idea: use a hash set to put all seen chars, check each char with the hash set to see if it has been seen before. -- This uses an additional data structure, a hash set.

Solution

first check if the string is an ASCII string or a Unicode string.
如果字符串长度超过字母表中所有字母的个数，则一定存在重复字符。
方法一：
使用boolean数组表示每个字符是否出现。例如如果字符串是ASCII则可以初始化一个长度为256的字符数组表示每个字符是否出现。-> 时间复杂度O(n), 空间复杂度O(1)

方法二：
使用bit vector表示一个字符是否出现，每一位表示一个字符。

如果不能使用额外的数据结构：

使用每个字符以此与其他字符进行比较 -> 时间复杂度O(n^2)
如果可以修改字符串，则可以先排序，再比较相邻字符，时间复杂度O(n * logn)

1.2 Check Permutation

Given two strings, write a method to decide if one is a permutation of the other
**Idea

如果两个字符串具有完全相同的字母组合则认为这两个字符串互为排列，因此，可以计算每个字符串里面字符出现的个数进行比较，字符串计数的方法通过一个int数组决定
可以先对两个字符串进行排列，排列后逐个字母进行对比

Solution
需要预先了解大小写和空格是否对结果有影响

1.3 URLify

URLify: Write a method to replace all spaces in a string with '%20'. You may assume that the string has sufficient space at the end to hold the additional characters, and that you are given the "true" length of the string. (Note: if implementing in Java, please use a character array so that you can perform this operation in place.)
EXAMPLE
Input: "Mr John Smith ", 13
Output: "Mr%20John%20Smith"

Idea
首先统计字符串中有多少个空格，由此推算将空格替换为%20后字符串有多长。如果原来字符串长度为len，其中有c个空格，那么处理后的字符串长度为len + 2c;因此我们可以得到扩展之后最后一个字符应该出现的位置。
对字符进行urlify的过程将从字符串的结尾向前进行。

1.4 Palindrome Permutation -> todo 实现优化算法的代码

EXAMPLE
Input: Tact Coa
Output: True (permutations: "taco cat'; "atco eta·; etc.)

Idea
对字符串中的数组进行计数，如果最多只有一个字符出现的次数为计数则认为这个字符串可以通过排列得到一个回文字符串。忽略其中的空白字符串

Solution
优化：使用bit vector表示一个字符出现次数的奇偶性

1.5 One Away -> todo 实现代码

There are three types of edits that can be performed on strings: insert a character, remove a character, or replace a character. Given two strings, write a function to check if they are one edit (or zero edits) away.
EXAMPLE
pale, ple -> true
pales, pale -> true
pale, bale -> true
pale, bae -> false

Idea:
因为判断只需要修改以此，那么首先判断两个字符串的长度差别是不是1，如果大于1则肯定不符合条件。
逐个判断两个字符串是否相等，如果不相等，则可以通过以下方式进行修改 => 首先假设字符串为A和B，当前比较的index为 i 和 j

如果A(i) 不等于 B(j)，但是A(i) = B(j+1)则可以通过向A中填充B(j）实现修改，i不变，j=j+1继续比较
如果A(i+1) = B(j+1)，则可以通过修改A(i) = B(j)达到目的
如果A(i+1) = B(j)则可以删除A(i)，那么i = i +1 继续比较

在出现一次edit后将一个flag变量设置为true，如果再次需要修改则返回false

Solution
长度差异决定需要修改的方式！！！

1.6 String Compression -> 实现代码

Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2blc5a3. If the "compressed" string would not become smaller than the original string, your method should return the original string. You can assume the string has only uppercase and lowercase letters (a - z).

Idea
注意：如果压缩之后字符串的长度不小于原字符串的长度则放弃压缩。

首先判断一个压缩后的字符串长度与原字符串长度的大小
如果需要则压缩字符串，使用一个int数组记录每个字符出现的个数

1.7 Rotate Matrix -> todo 实现代码

Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

1.8 Zero Matrix -> todo 实现代码

Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0.

Idea
使用第一行和第一列作为标志位，并使用isColZero和isRowZero两个标志表示第一列和第一行本身是否为0.
首先遍历整个数组，如果一个元素为0，则将它所在的第一行和第一列对应的位置设置为0。
再次遍历数组，根据第一行和第一列的标志信息将对应的行和列设置为0

1.9 String Rotation

Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, 51 and 52, write code to check if 52 is a rotation of 51 using only one call to isSubstring (e.g., "waterbottle" is a rotation of" erbottlewat").

解法厉害！