Leetcode: Ransom Note

Given
 an 
arbitrary
 ransom
 note
 string 
and 
another 
string 
containing 
letters from
 all 
the 
magazines,
 write 
a 
function 
that 
will 
return 
true 
if 
the 
ransom 
 note 
can 
be 
constructed 
from 
the 
magazines ; 
otherwise, 
it 
will 
return 
false. 



Each 
letter
 in
 the
 magazine 
string 
can
 only 
be
 used 
once
 in
 your 
ransom
 note.

简单题，只需判断magazine里是否包含ransom note。对于26个字母不需要使用hash map，直接用一个数组即可。

public class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] magazineCount = new int[26];
        for (int i = 0; i < magazine.length(); i++) {
            magazineCount[magazine.charAt(i) - 'a']++;
        }
        for (int i = 0; i < ransomNote.length(); i++) {
            if (--magazineCount[ransomNote.charAt(i) - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}

Reverse Vowels of a String

Write a function that takes a string as input and reverse only the vowels of a string.

简单题

public class Solution {
    public String reverseVowels(String s) {
        int start = 0, end = s.length() - 1;
        StringBuilder builder = new StringBuilder(s);
        while (start < end) {
            while (start < end && !"aeiouAEIOU".contains(s.substring(start, start+1))) {
                start++;
            }
            while (start < end && !"aeiouAEIOU".contains(s.substring(end, end+1))) {
                end--;
            }
            char a = builder.charAt(start);
            builder.setCharAt(start, builder.charAt(end));
            builder.setCharAt(end, a);
            start++;
            end--;
        }
        return builder.toString();
    }
}

Lintcode: two strings are anagram

没有难度

public class Solution {
    public boolean anagram(String s, String t) {
        if (s == null || t == null || s.length() != t.length()) {
            return false;
        }
        char[] s1 = s.toCharArray();
        char[] t1 = t.toCharArray();
        Arrays.sort(s1);
        Arrays.sort(t1);
        return String.valueOf(s1).equals(String.valueOf(t1));
    }
}

Lintcode: compare strings

没有难度。

public class Solution {
    public boolean compareStrings(String A, String B) {
        if (A == null || B == null || A.length() < B.length()) {
            return false;
        }
        if (B.length() == 0) {
            return true;
        }
        int[] store = new int[26];
        for (int i = 0; i < A.length(); i++) {
            store[A.charAt(i) - 'A']++;
        }
        for (int i = 0; i < B.length(); i++) {
            store[B.charAt(i) - 'A']--;
            if (store[B.charAt(i) - 'A'] < 0) {
                return false;
            }
        }
        return true;
    }
}

Lintcode: Longest common substring

用的一维dp。如果用KMP会优化很多。

public class Solution {
    public int longestCommonSubstring(String A, String B) {
        if (A == null || A.length() == 0 || B == null || B.length() == 0) {
            return 0;
        }
        int[] store = new int[A.length()];
        int res = 0;
        for (int i = 0; i < B.length(); i++) {
            int tmpMax = 0;
            for (int j = A.length() - 1; j >= 0; j--) {
                if (B.charAt(i) == A.charAt(j)) {
                    store[j] = j == 0 ? 1 : store[j-1] + 1;
                    tmpMax = Math.max(tmpMax, store[j]);
                } else {
                    store[j] = 0;
                }
            }
            res = Math.max(res, tmpMax);
        }
        return res;
    }
}

ZigZag Conversion

The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P A H N
A P L S I I G
Y I R
And then read line by line: “PAHNAPLSIIGYIR”
Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);
convert(“PAYPALISHIRING”, 3) should return “PAHNAPLSIIGYIR”.

---

public class Solution {
    public String convert(String s, int nRows) {
        if (nRows <= 1 || s == null) {
          return s;
        }
        StringBuilder sb = new StringBuilder();
        nRows--;
        for (int i = 0; i <= nRows; i++) {
          for (int j = i; j < s.length(); j+=nRows*2) {
            sb.append(s.charAt(j));
            if (i != 0 && i != nRows && j + (nRows-i)*2 < s.length()) {
              sb.append(s.charAt(j + (nRows-i)*2));
            }
          }
        }
        return sb.toString();
    }
}

1.8 Check string rotation

Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s i and s2, write code to check if s2 is a rotation of si using only one call to isSubstring (e.g.,”waterbottle”is a rota- tion of”erbottlewat”).

---

如果s2是s1的rotation，那么s2必然是s1+s1的substring。很巧妙

public boolean isRotation(String s1, String s2) {
	if (s1 == null || s2 == null) {
		return s1 == null && s2 == null;
	}
	if (s1.length() != s2.length()) {
		return false;
	}
	return isSubstring(s1+s1, s2);
}

1.4 compress string

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 orig- inal string, your method should return the original string.

---

public String compressString(String s) {
	if (s == null) {
		return s;
	}
	StringBuilder sb = new StringBuilder();
	for (int i = 0; i < s.length(); i++) {
		sb.append(s.charAt(i));
		int j = i+1;
		while (j < s.length() && s.charAt(j) == s.charAt(i)) {
			j++;
		}
		sb.append(j - i);
		i = j-1;
	}
	return sb.length() > s.length() ? s : sb.toString();
}

1.4 Replace space

Write a method to replace all spaces in a string with’%20′. You may assume that the string has sufficient space at the end of the string to hold the additional characters, and that you are given the “true” length of the string. (Note: if imple- menting in Java, please use a character array so that you can perform this opera- tion in place.)
EXAMPLE
Input: “Mr John Smith” Output: “Mr%20Dohn%20Smith”

---

parse两遍，第一遍算出需要长度，第二遍从后往前fill

public void replaceSpace(char[] str, int len) {
	int total = 0;
	for (int i = 0; i < str.length; i++) {
		if (str[i] == ' ') {
			total += 2;
		}
	}
	int i = len - 1;
	for (int index = len + total - 1; index >= 0; index--) {
		if (str[i] == ' ') {
			str[index--] = '0';
			str[index--] = '2';
			str[index] = '%';
		} else {
			str[index] = str[i];
		}
		i--;
	}
}

1.3 Check Permutation

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

---

第一种解法是先sort，再比较两个string是否equal。复杂度较高。解法二只需要先遍历s1，对出现的字符记录一个count。遍历s2的时候count－－，如果遇到count小于0，return false。

public boolean isPermutation(String s1, String s2) {
	if (s1 == null || s2 == null) {
		return s1 == null && s2 == null;
	}
        if (s1.length() != s2.length()) {
                return false;
        }
	char[] c1 = s1.toCharArray();
	char[] c2 = s2.toCharArray();
	Arrays.sort(c1);
	Arrays.sort(c2);
	return new String(c1).equals(new String(C2));
}