每日一题5
今天看看比较字符串。
还是老样子，运用简单粗暴法。
直接想到遍历B，逐个去跟A做对比。这里的话不太熟悉JAVA的String类的方法，后面找了一下，发现真的有可以从字符串中取出特定索引的方法，于是这个想法可行。紧接着又遇到一个问题，就是按照题目中，若B含有两个“A”，A中只有一个，也算是false，这就说明，A中对应的元素个数必须与B中对应。这里就想到用一个标记数组 arr[]，一开始全部设置为0，遍历B找A中对应时，遇到相同且arr[i]为0的就返回true，并且进行下一个B中的字母遍历。上代码：
public class Solution {
/**
* @param A: A string
* @param B: A string
* @return: if string A contains all of the characters in B return true else return false
*/
public boolean compareStrings(String strA, String strB) {
int aLen = strA.length();
int[] arr = new int[aLen];
for (int i = 0; i < aLen; i++) {
arr[i] = 0;
}
boolean flag = true;
for (int i = 0, bLen = strB.length(); i < bLen; i++) {
flag = false;
for(int j = 0;(j < aLen) && (!flag);j ++){
if (strB.charAt(i) == strA.charAt(j) && arr[j] == 0) {
arr[j] = 1;
flag = true;
}
}
if (!flag) {
break;
}
}
return flag;
}
}
然后觉得不够优化，去网上看了一个解法，醍醐灌顶。这里思路我个人觉得跟桶排序的感觉很像，但不是处理排序。他把A中的元素逐个与“A”做差，差值作为数组index的索引，也就是说index[0]就是"A"，index[1]就是“B”，如此往下，然后index的索引最大为26，也就是26个字母，遍历A，当A中有重复的元素，就在对应索引上加1。加完以后，再遍历B，同样，B中每个元素与"A"做差，使对应差值为索引的元素减1。如果最后index数组中所有索引对应的元素都大于0，说明A中肯定包含了B中所有的元素，反之则为false。太棒了！！！！
public class Solution {
/**
* @param A : A string includes Upper Case letters
* @param B : A string includes Upper Case letter
* @return : if string A contains all of the characters in B return true else return false
*/
public boolean compareStrings(String A, String B) {
// write your code here
int[] index = new int[26];
for (int i = 0; i < A.length(); i++) {
index[A.charAt(i) - 'A']++;
}
for (int i = 0; i < B.length(); i++) {
index[B.charAt(i) - 'A']--;
if(index[B.charAt(i) - 'A'] < 0){
return false;
}
}
return true;
}
}
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-11-13，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读