p318

发表于 | 分类于 |

LeetCode 318 Maximum Product of Word Lengths 题解

1.题目：

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.
Example 1:
Given [“abcw”, “baz”, “foo”, “bar”, “xtfn”, “abcdef”]
Return 16
The two words can be “abcw”, “xtfn”.
Example 2:
Given [“a”, “ab”, “abc”, “d”, “cd”, “bcd”, “abcd”]
Return 4
The two words can be “ab”, “cd”.
Example 3:
Given [“a”, “aa”, “aaa”, “aaaa”]
Return 0

题意：

输入一个字符串数组，输出可以返回的两个字符串长度的最大乘积，要求这两个字符串没有用到重复的数组。

2.解题思路:

感觉我是暴力过的TUT。放上没有AC，和小改动就AC的代码

3.代码

[title] [] [url] [link text]
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
//AC代码
public class Solution {
    public int maxProduct(String[] words) {
		int ans = 0;
		int max = 0;
		int len = words.length;
		for (int i = 0; i < len; i++) {
			for (int j = i + 1; j < len; j++) {
				if (words[i].length() * words[j].length()>max&&check(words[i], words[j])) {//在条件处进行优化
					ans = words[i].length() * words[j].length();
					
						max = ans;
				}
			}
		}
		return max;
	}

	public boolean check(String s1, String s2) {
		HashSet<Character> hashSet = new HashSet<Character>();
		for (int i = 0; i < s1.length(); i++) {
			hashSet.add(s1.charAt(i));
		}
		for (int i = 0; i < s2.length(); i++) {
			if (hashSet.contains(s2.charAt(i)))
				return false;
		}
		return true;
	}
}

//没有AC
public class Solution {
    public int maxProduct(String[] words) {
		int ans = 0;
		int max = 0;
		int len = words.length;
		for (int i = 0; i < len; i++) {
			for (int j = i + 1; j < len; j++) {
				if (check(words[i], words[j])) {
					ans = words[i].length() * words[j].length();
					if (max < ans)
						max = ans;
				}
			}
		}
		return max;
	}

	public boolean check(String s1, String s2) {
		HashSet<Character> hashSet = new HashSet<Character>();
		for (int i = 0; i < s1.length(); i++) {
			hashSet.add(s1.charAt(i));
		}
		for (int i = 0; i < s2.length(); i++) {
			if (hashSet.contains(s2.charAt(i)))
				return false;
		}
		return true;
	}
}

4.一些总结：