Leetcode String

[zxw018018]

LeetCode String

String

1. initialize

String s1 = "Hello World";
String s2 = s1;                //reference
String s3 = new String(s1);    //copy

2. compare using ==

s1 == "Hello World";    //true
s1 == s2;               //true because of reference
s1 == s3;               //false

3. compare using equals

s1.equals("Hello World");    //true
s1.equals(s2);               //true
s1.equals(s3);               //true

4. compare using compareTo

s1.compareTo("Hello World");    //0
s1.compareTo(s2);               //0
s1.compareTo(s3);               //0

• if s1 > s2, it returns positive number
• if s1 < s2, it returns negative number
• if s1 == s2, it returns 0

5. concatenate

s1 += "!";     //"Hello World!"

• Time complexity is O(n^2)

6. find

s1.indexOf('o');        //4
s1.lastIndexOf('o');    //7

7. get substring

s1.substring(6, 11);    //"World"

• Time complexity of find and substring are O(n)

8. convert to a char array to be mutable

String s = "Hello World";
char[] str = s.toCharArray();
str[5] = ',';       //"Hello,World"

9. use StringBuilder if concatenate often

int n = 2;
StringBuilder str = new StringBuilder();
for (int i = 0; i < n; i++) {
    str.append("hello");
}
String s = str.toString();    //"hellohello"

• Time complexity O(n)

Problems

5. Longest Palindromic Substring

Description

• Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Analysis

• Use dynamic programming to store if j from i is palindrome.

8. String to Integer (atoi)

Description

• Implement atoi which converts a string to an integer.
• The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
• The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
• If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
• If no valid conversion could be performed, a zero value is returned.

Analysis

• Consider if the string is empty
• ignore all whitespaces
• get the sign
• check if the number exceeds the max or min integer value.

10. Regular Expression Matching

Description

• Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.

Analysis

• Use recursion
• Check if the pattern is empty
• First match: text is not empty and the first pattern character matches the first text character or the first pattern character is .

1. Pattern length < 2: first match and the substring of pattern and the sub of text matches
2. Pattern length >= 2 and contains *: first match and the substring of text and and pattern matches or text match the rest of pattern except *

12. Integer to Roman

Description

• Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol	Value
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

Analysis

String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

13. Roman to Integer

Description

• Roman number to integer number.

Analysis

• First add the number. If it is smaller than the number behind it, subtract 2* it.

14. Longest Common Prefix

Description

• Write a function to find the longest common prefix string amongst an array of strings.
• If there is no common prefix, return an empty string "".

Analysis

• From position 0, check all string until characters are not the same.

28. Implement strStr()

Description

• Implement strStr().
• Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Analysis

• Use two pointers.

38. Count and Say

Description

• The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     111221

Analysis

• Just iterate through.

44. Wildcard Matching

Description

• Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.

Analysis

• Iterate through s, first skip *, then find if there is a match. Finally skip * again.

49. Group Anagrams

Description

• Given an array of strings, group anagrams together.

Analysis

• Use HashMap and sort string.

58. Length of Last Word

Description

• Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.
• If the last word does not exist, return 0.

Analysis

• Use trim()

65. Valid Number

Description

• Validate if a given string can be interpreted as a decimal number.

Analysis

• Use DFA
  

67. Add Binary

Description

• Given two binary strings, return their sum (also a binary string).
• The input strings are both non-empty and contains only characters 1 or 0.

Analysis

• Use charAt() and reverse()

71. Simplify Path

Description

• Given an absolute path for a file (Unix-style), simplify it.

Analysis

• Use stack.

125. Valid Palindrome

Description

• Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
• Note: For the purpose of this problem, we define empty string as valid palindrome.

Analysis

• Use two pointers.

151. Reverse Words in a String

Description

• Given an input string, reverse the string word by word.
  Note:
• A word is defined as a sequence of non-space characters.
• Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
• You need to reduce multiple spaces between two words to a single space in the reversed string.

Analysis

• Use trim() and split().

205. Isomorphic Strings

Description

• Given two strings s and t, determine if they are isomorphic.
• Two strings are isomorphic if the characters in s can be replaced to get t.
• All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

Analysis

• Use two hashmaps.

242. Valid Anagram

Description

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

Analysis

• Create an array which length is 26 to store how many times the alphabets show.

290. Word Pattern

Description

• Given a pattern and a string str, find if str follows the same pattern.
• Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Analysis

• Use two hashmaps.

344. Reverse String

Description

• Write a function that takes a string as input and returns the string reversed.

Analysis

• Use two pointers.

557. Reverse Words in a String III

Description

• Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Analysis

• Use StringBuilder, split(), StringBuffer, reverse()