Leetcode 242 - Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

做法1：

把两个string都sort好，然后比较之。
Time: O(nlogn)
Space: O(1)

这样的话答案78.41%

public class Solution {
    public boolean isAnagram(String s, String t) {
        char[] ss = s.toCharArray();
        Arrays.sort(ss);
        String sss = new String(ss);
        char[] tt = t.toCharArray();
        Arrays.sort(tt);
        String ttt = new String(tt);
        return sss.equals(ttt);
    }
}

做法2： 用一个数组存起来
似乎比sort还要慢一些, 46.32%, 8ms。

public class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        else if (s.length() == 0) return true;
        int[] numbychar = new int[256];
        int num_unique = 0;
        int num_complete = 0;
        char[] s_char = s.toCharArray();
        for (char c : s_char) {
            if (numbychar[c] == 0) num_unique++;
            ++numbychar[c];
        }
        for (int i = 0; i < t.length(); i++) {
            int c = (int) t.charAt(i);
            if (numbychar[c] == 0) return false;
            --numbychar[c];
            if (numbychar[c] == 0) {
                ++num_complete;
                if (num_complete == num_unique) {
                    return i==t.length()-1;
                }
            }
        }
        return false;
    }
}

Improve the 2nd solution: use a hashtable

import java.util.*;
public class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length()!=t.length()) return false;
        
        Hashtable 
            theTableS = new Hashtable(),
            theTableT = new Hashtable();
        for (char i:s.toCharArray()) {
            if (theTableS.containsKey(i))
                theTableS.put(i,theTableS.get(i)+1);
            else theTableS.put(i,1);
        }
        for (char i:t.toCharArray()) {
            if (theTableT.containsKey(i)) 
                theTableT.put(i,theTableT.get(i)+1);
            else theTableT.put(i,1);
        }
        return theTableT.equals(theTableS);
    }
}

Leetcode 73 - Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Naive Approach:
For word1, use insert/delete/replace to generate all strings as its children, then for each children, generate all strings etc...
But the tree will expand too fast.
Solutions:
1. DP
2. Pruning (delete the nodes that are not actual English words).

Regular Expression

"a*" - zero or more a
"a+" - 1 or more a's
"[a-f]" - Any character between a and f
"[^a-cz]" - Any character which is not between a and c, and not z
"[abc]+" - 1 or more of a, b or c in a row
"abc" - character abc in a row
"a|b" - Character a or character b

Java:
java.util.regex
java.util.regex.Matcher;
java.util.regex.Pattern;

protected List getTokens(String pattern)
 {
  ArrayList tokens = new ArrayList();
  Pattern tokSplitter = Pattern.compile(pattern);
  Matcher m = tokSplitter.matcher(text);
  
  while (m.find()) {
   tokens.add(m.group());
  }
  
  return tokens;
 }

String

在Java里，String是一个类(class)。这个类包含char数组(array)，以及其他的字段(fields)和方法(methods)。

常用方法(Java):
toCharArray() //get char array of a String charAt(int x) //get a char at the specific index length() //string length length //array size 
indexOf(String s) // return the index of the substring s in string.
split(String pattern) // split the String with string pattern. substring(int beginIndex) substring(int beginIndex, int endIndex) Integer.valueOf()//string to integer String.valueOf()/integer to string Arrays.sort() //sort an array Arrays.toString(char[] a) //convert to string Arrays.copyOf(T[] original, int newLength) System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

注意事项(Java):
1. String is immutable. 也就是说string在被创建以后，在heap上不能被改变，任何的改变都会创建一个新的string object。
2. 如果想用可以改变的String，就需用StringBuffer或者StringBuilder。
3. String immutable的原因:
    1) Efficiency: Caching hashcode;
    2) Security: Security; thread safe; no violation for other objects (HashSet etc.)
4. 初始化String，用"" 还是 new String():
    主要在于interning，如果用"sss"，那么会指向heap上已有的"sss"，这样的话==是true。否则，会有两个"sss", equals()为true，但是==为false。
5. Array用length (length是Array object的一个final instance variable(不会变)). String用length()，是String这个class的一个method。
6. Varargs (Variable Arguments)
    As its definition indicates, varargs is useful when a method needs to deal with an arbitrary number of objects. One good example from Java SDK is String.format(String format, Object... args). The string can format any number of parameters, so varargs is used.

String.format("An integer: %d", i); String.format("An integer: %d and a string: %s", i, s);

常见问题:
1. 转化一个char[] to String

public static void main(String[] args) {
  char[] myString = new char[] {'T', 'H', 'I', 'S', ' ',  'I', 'S', ' ', 'T', 'E', 'S', 'T'};
 
  String output1 = new String(myString);
  System.out.println("output1 : " + output1);
 
  String output2 = String.valueOf(myString);
  System.out.println("\noutput2 : " + output2);
 }

2. 转化String to char[]
toCharArray()

3. String to int
Integer.valueof(s);
or
Integer.parseInt(s);

4. String相关的问题，经常会用到char[]，经常会遍历，用几个pointer标记位置的方法也是常用的。

5. for-each
char[] cArray = s.toCharArray();
for (char c : cArray)
这里c gets a copy of each value in cArray!

I/O Classes and Objects in Java and Read a Line

System.out is a PrintStream object that outputs to the screen

System.in is an InputStream object that reads from the keyboard

But System.in doesn't have methods to read a line directly.  There is a method
called readLine that does, but it is defined on BufferedReader objects.

- How do we construct a BufferedReader?  One way is with an InputStreamReader.
- How do we construct an InputStreamReader?  We need an InputStream.
- How do we construct an InputStream?  System.in is one.
(You can figure all of this out by looking at the constructors in the online
Java libraries API--specifically, in the java.io library.)

InputStream objects (e.g. System.in) read raw data from some source (like Keyboard), but don't format the data.
InputStreamReader objects compose the raw data into characters (2 bytes long in Java).
BufferedReader objects compose the characters into entire lines of text.

Java program that reads a line from the keyboard and prints it on the screen.

 import java.io.*;

class SimpleIO {
     public static void main(String[] args) throws Exception {
          BufferedReader keybd = 
               new BufferedReader(new InputStreamReader(System.in));
          System.out.println(keybd.readLine());
     }
}

How to read a line of text: With readLine on BufferedReader
How to create a BufferedReader: With an InputStreamReader
How to create a InputStreamReader: With an InputStream
How to create InputStream: With a URL

public class BufferedReader extends Reader

BufferedReader is a class 

Code:

import java.net.*;
import java.io.*;
class WHWWW {
    public static void main(String[] arg) throws Exception {
        URL u = new URL("http://www.whitehouse.gov/");
        InputStream ins = u.openStream();
        InputStreamReader isr = new InputStreamReader(ins);
        BufferedReader whiteHouse = new BufferedReader(isr);
        System.out.println(whiteHouse.readLine());
    }
}