String II

发表于   |  

括号匹配

#20 Valid Parentheses

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.
The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.

借用栈来实现。若是合法的括号，左右括号必然是对称的。遍历字符串，遇到左括号即压入栈内；遇到右括号则与栈顶元素匹配，若匹配则弹出，否则返回false。
需要注意到一些特殊情况，比如：”(“ “)”这样的。若到了最后，栈中仍有括号，说明不合法；在弹栈前要确认栈内不为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean isValid(String s) {
       Stack<Character> stack = new Stack<Character>();
       for (int i = 0; i < s.length(); i++) {
           char c = s.charAt(i);
           if (c == '(' || c == '[' || c == '{') {
               stack.push(c);
           }
           else {
               if (stack.isEmpty())
                   return false;
               char pre = stack.pop();
               if ((c == ')' && pre == '(') || (c == ']' && pre == '[') || (c == '}' || pre == '{'))
                   continue;
               else
                   return false;
           }
       }
       return stack.isEmpty();
   }

最长无重复字符串匹配

#3 Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

用两个变量来圈定当前正在判断的无重复字符串。
设一个hash表，来记录各字符上一次出现的位置。在遍历字符串时，查询当前字符在表中的值。
若该字符上一次出现的位置在圈定范围内，说明出现了重复字符，将left重定向到前面重复字符的下一个位置。更新hash表，然后继续向下判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int lengthOfLongestSubstring(String s) {
       if (s.length() == 0)
           return 0;
       int left = 0, max = 1;
       int[] hash = new int[128];
       for (int i = 0; i < hash.length; i++)
           hash[i] = -1;
       for (int i = 0; i < s.length(); i++) {
           if (hash[s.charAt(i)] >= left) {
               max = Math.max(max, i - left);
               left = hash[s.charAt(i)] + 1;
           }
           hash[s.charAt(i)] = i;
       }
       return Math.max(max, s.length() - left);
   }

是否是合法回文

#125 Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
“A man, a plan, a canal: Panama” is a palindrome.
“race a car” is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.

设两个变量分别指向头尾，然后逐渐匹配向中间靠拢。
注意数字也要判断，忽略空格和字符。
原来我对字符的判断是这样写的：(s.charAt(right) < ‘0’ || (s.charAt(right) > ‘9’ && s.charAt(right) < ‘a’) || s.charAt(right) > ‘z’)
后来发现Character类自带字母与数字判断函数：Character.isLetterOrDigit(c);
看来还是要把库函数记熟才好啊~什么时候整理一下~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean isPalindrome(String s) {
       int left = 0, right = s.length()-1;
       while (left <= right) {
           while (left < right && !Character.isLetterOrDigit(s.charAt(left)))
               left++;
           while (left < right && !Character.isLetterOrDigit(s.charAt(right)))
               right--;
           
           if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
               return false;
           }
           left++;
           right--;
       }
       return true;
   }

今天收集了网上WAP面经里提到的题目，明天开刷 ~