StringIII

发表于   |  
  • Reverse Words in a String
  • Longest Common SubSequence

Reverse Words in a String

Reverse Words in a String

Given an input string, reverse the string word by word.
For example,
Given s = “the sky is blue”,
return “blue is sky the”.

之前有遇到这个题目，现在看到别人家的simple solution之后，发现用暴力解题的我真是太low了。
利用正则表达式，直接调用String类自带的工具–split()方法。

split() – “将字符串从正则表达式匹配的地方切开。”
–《Thinking in Java》

在这题中，就可以使用该方法，将String字符串从根据空格切割成String数组，每个元素就是一个单词(貌似不用考虑标点？)。
最后倒序输出就可以了。

1
2
3
4
5
6
7
8
public String reverseWords(String s) {
       String[] word = s.split("\\s+");
       StringBuilder sb = new StringBuilder();
       for (int i = word.length-1; i >= 0; i--) {
           sb.append(word[i]).append(" ");
       }
       return sb.toString().trim();
   }

题外话
当输入为” “时

  • s.trim().split();
  • s.split();

这两句产生的结果是不一样的。
输入返回的数组的长度，前者的长度为1，而后者的长度为0。
trim()方法的作用是取出首尾空格。当它被执行于” “时，得到一个空字符串，这时split()是没有进行切割的，所以最后得到一个含有空串的数组。
没有trim()时，split()对它进行切割(我理解为把空格给剔除了)，这时因为空格前后是没有字符的，所以最后得到一个空数组。
特殊情况还是要多想想啊~

最长公共子序列

看到WPA题库里会有这题，就刷了一下。

一个数列S，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则S称为已知序列的最长公共子序列。
– wiki

最长公共子序列(Longest Common SubSequence)和最长公共子串(Longest Common SubString)是不一样的，前者不要求连续。
比如：

  • abcde
  • akkbckk
    abc即是它们的公共子串。

如果用暴力破解的话，时间复杂度到了指数级的高度。一般是用动规来解决(貌似是动规经典题？)。

公共子序列长度

首先是先考虑得到最长公共子序列的长度。
利用动规的思想，将问题分割为子问题，然后在子问题的解上判断。
对于字符串a和b，记录下a前i个和b前j个的子串所拥有的最长公共子序列，然后在子串的基础上判断之后字符串。

  • 若a[i] == b[j]，说明a[i]也是公共子序列的元素之一，就可以在长度a[i-1]和b[j-1]的子串所记录的lcs长度上加一。
  • 若a[i] != b[j]，则要在(a[i-1]&b[j])和(a[i]&b[j-1])两种情况下取较大值做自己的最长公共子序列长度。
    设一个二维数组dp来记录前i位a和前j位b的最长公共子序列长度。
    然后可以归纳为：
  • i = 0 || j = 0 – dp[i][j] = 0;
  • a[i] == b[j] – dp[i][j] = dp[i-1][j-1];
  • a[i] != b[j] – dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    最后，dp[m]n即是ab字符串的最长公共子序列的长度了。
1
2
3
4
5
6
7
8
9
10
11
12
13
public void lcs(String a, String b) {
	int lenA = a.length(), lenB = b.length();
	int[][] dp = new int[lenA+1][lenB+1];
	for (int i = 1; i <= lenA; i++) {
		for (int j = 1; j <= lenB; j++) {
			if (a.charAt(i-1) == b.charAt(j-1))
				dp[i][j] = dp[i-1][j-1] + 1;
			else
				dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
		}
	}
	System.out.println(dp[lenA][lenB]);
}

输出最长公共子序列

如果要输出最长公共子序列，那就需要知道得到该子序列的路径，即dp[i][j]是从dp的哪个位置的得到的。
所以在记录dp时，我们可以另设一个二维数组记录方向，因为每次都只会来自左，上，及左上方，所以要记录这三个方向。

  • 来自dp[i-1][j-1]， director[i][j] = “left_up”;
  • 来自dp[i-1][j], director[i][j] = “up”;
  • 来自dp[i][j-1], director[i][j] = “left”;
    然后再根据director所指的方向(从右下角开始走)，找到对应的字符就可以了(注意这时是倒序)。

    0 0 0 0 0 0 0
    0 0 0 0 1 1 1
    0 1 1 1 1 2 2
    0 1 1 2 2 2 2
    0 1 1 2 2 3 3
    0 1 2 2 2 3 3
    0 1 2 2 3 3 4
    0 1 2 2 3 4 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public void lcs(String a, String b) {
	int lenA = a.length(), lenB = b.length();
	int[][] dp = new int[lenA+1][lenB+1];
	String[][] director = new String[lenA+1][lenB+1]; 
	for (int i = 1; i <= lenA; i++) {
		for (int j = 1; j <= lenB; j++) {
			if (a.charAt(i-1) == b.charAt(j-1)) {
				dp[i][j] = dp[i-1][j-1] + 1;
				director[i][j] = "left_up";
			}
			else  {
				if (dp[i-1][j] >= dp[i][j-1]) {
					dp[i][j] = dp[i-1][j];
					director[i][j] = "up";
				}
				else {
					dp[i][j] = dp[i][j-1];
					director[i][j] = "left";
				}
			}
		}
	}
	printSubsequence(director, a, b);
}

public void printSubsequence(String[][] director, String a, String b) {
	int lenA = a.length(), lenB = b.length();
	StringBuilder sb = new StringBuilder();
	while (lenA != 0 && lenB != 0) {
		
		if (director[lenA][lenB].equals("left_up"))  {
			sb.append(a.charAt(lenA-1));
			lenA--;
			lenB--;
		}
		else if (director[lenA][lenB].equals("left")) {
			lenB--;
		}
		else {
			lenA--;
		}
	}
	System.out.println(sb.reverse().toString());
}