一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 316|回复: 9
收起左侧

[算法题] Compare strings

[复制链接] |试试Instant~ |关注本帖
love1point 发表于 2015-6-11 20:52:45 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 love1point 于 2015-6-11 20:53 编辑

这道题链接:http://www.lintcode.com/en/problem/compare-strings/

我的算法: 用HashMap, Key是String, Value 是 String 的个数。如果A 的 个数小于B, 返回false,反之true。

但我总觉得我的算法虽然很简单,但实现起来觉得代码太冗余,有人给个简单的思路不?



Compare StringsShow result

26%Accepted

Compare two strings A and B, determine whether A contains all of the characters in B.
The characters in string A and B are all Upper Case letters.

Have you met this question in a real interview?
Yes


Example
For A = "ABCD", B = "ACD", return true.
For A = "ABCD", B = "AABC", return false.


Note
The characters of B in A are not necessary continuous or ordered.
  1. public class Solution {
  2.     /**
  3.      * @param A : A string includes Upper Case letters
  4.      * @param B : A string includes Upper Case letter
  5.      * [url=home.php?mod=space&uid=160137]@return[/url] :  if string A contains all of the characters in B return true else return false
  6.      */
  7.     public boolean compareStrings(String A, String B) {
  8.         // write your code here
  9.         if(A == null && B == null || A.length() == 0 && B.length() == 0)
  10.         {
  11.             return true;
  12.         }
  13.         
  14.         if(A == null || A.length() == 0)
  15.         {
  16.             return false;
  17.         }
  18.         
  19.         
  20.         
  21.         HashMap<Character, Integer> mapA = new HashMap<Character, Integer>();
  22.         HashMap<Character, Integer> mapB = new HashMap<Character, Integer>();
  23.         
  24.         for(int i = 0; i < A.length(); i++)
  25.         {
  26.             if(mapA.containsKey(A.charAt(i)))
  27.             {
  28.                 mapA.put(A.charAt(i),mapA.get(A.charAt(i))+1);
  29.             }
  30.             else
  31.             {
  32.                 mapA.put(A.charAt(i), 1);
  33.             }
  34.         }
  35.         
  36.         for(int i = 0; i < B.length(); i++)
  37.         {
  38.             if(mapB.containsKey(B.charAt(i)))
  39.             {
  40.                 mapB.put(B.charAt(i),mapB.get(B.charAt(i))+1);
  41.             }
  42.             else
  43.             {
  44.                 mapB.put(B.charAt(i), 1);
  45.             }
  46.         }
  47.         
  48.         for(int i = 0; i < B.length(); i++)
  49.         {
  50.             if(mapA.containsKey(B.charAt(i)))
  51.             {   if(mapA.get(B.charAt(i)) >= mapB.get(B.charAt(i)))
  52.                 {
  53.                     continue;
  54.                 }
  55.                 else
  56.                 {
  57.                     return false;
  58.                 }
  59.             }
  60.             else
  61.             {
  62.                 return false;
  63.             }
  64.         }
  65.         return true;
  66.         
  67.     }
  68. }
复制代码




stellari 发表于 2015-6-11 21:41:31 | 显示全部楼层
  1.    
  2. bool compareStrings(string A, string B) {
  3.         // write your code here
  4.         char histA[26]={0};
  5.         for (auto c: A) {
  6.             histA[c-'A']++;
  7.         }
  8.         for (auto c: B) {
  9.             histA[c-'A']--;
  10.             if (histA[c-'A'] < 0) return false;
  11.         }
  12.         return true;
  13.     }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-11 21:48:32 | 显示全部楼层
看了网上解法,只用一个HashMap就可以,三重循环降到两重循环。就是如果A中有B的string,就把相应的Value减1, 如果A中的Value减到1, 可B还有此string, 则false, 反之true。时间和空间都是O(n), n为A的长度?
  1. public class Solution {
  2.     /**
  3.      * @param A : A string includes Upper Case letters
  4.      * @param B : A string includes Upper Case letter
  5.      * @return :  if string A contains all of the characters in B return true else return false
  6.      */
  7.     public boolean compareStrings(String A, String B) {
  8.         // write your code here
  9.         if(A == null && B == null || A.length() == 0 && B.length() == 0)
  10.         {
  11.             return true;
  12.         }
  13.         
  14.         if(A == null || A.length() == 0)
  15.         {
  16.             return false;
  17.         }
  18.         
  19.         
  20.         
  21.         HashMap<Character, Integer> mapA = new HashMap<Character, Integer>();
  22.         
  23.         for(int i = 0; i < A.length(); i++)
  24.         {
  25.             if(mapA.containsKey(A.charAt(i)))
  26.             {
  27.                 mapA.put(A.charAt(i),mapA.get(A.charAt(i))+1);
  28.             }
  29.             else
  30.             {
  31.                 mapA.put(A.charAt(i), 1);
  32.             }
  33.         }
  34.         
  35.         
  36.         for(int i = 0; i < B.length(); i++)
  37.         {
  38.             if(mapA.containsKey(B.charAt(i)))
  39.             {   if(mapA.get(B.charAt(i)) == 0 )
  40.                 {
  41.                     return false;
  42.                 }
  43.                 mapA.put(B.charAt(i), mapA.get(B.charAt(i))-1);
  44.             }
  45.             else
  46.             {
  47.                 return false;
  48.             }
  49.         }
  50.         return true;
  51.         
  52.     }
  53. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-11 21:52:43 | 显示全部楼层

感谢回复

我也有在网上看过这个解法,但不怎么好理解和记忆,对于我
http://blog.xiaohuahua.org/2015/02/10/lintcode-compare-strings/
回复 支持 反对

使用道具 举报

stellari 发表于 2015-6-12 00:07:01 | 显示全部楼层
love1point 发表于 2015-6-11 21:52
感谢回复

我也有在网上看过这个解法,但不怎么好理解和记忆,对于我

为什么说不好理解呢?你三楼中的解法和我的解法是一模一样的啊。只不过你是用了一个HashMap,所以要额外判断某个字符是否已经存在于HashMap中;而我用的是一个char[26],不需要额外判断这一点。除此以外,在代码逻辑上没有任何区别。
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-12 09:16:03 | 显示全部楼层
stellari 发表于 2015-6-12 00:07
为什么说不好理解呢?你三楼中的解法和我的解法是一模一样的啊。只不过你是用了一个HashMap,所以要额外 ...

char histA[26]={0};

这句能解释一下吗?谢谢
回复 支持 反对

使用道具 举报

stellari 发表于 2015-6-12 09:48:20 | 显示全部楼层
love1point 发表于 2015-6-12 09:16
char histA[26]={0};

这句能解释一下吗?谢谢

初始化一个长为26的数组,使其中的每个元素均为0。
另外抱歉我把类型写错了。应该是
int histA[26] = {0};
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-12 09:50:21 | 显示全部楼层
stellari 发表于 2015-6-12 09:48
初始化一个长为26的数组,使其中的每个元素均为0。
另外抱歉我把类型写错了。应该是
int histA[26] = { ...

好的,感谢再次回复哈。
我通常这样写,int[] hist = new int[26].
然后默认的所有元素都是0
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-12 09:54:42 | 显示全部楼层

auto c: A 里的auto 是啥?你这是啥语言的语法 ? 不该是Character 或char?
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-12 10:12:31 | 显示全部楼层

按照你的思想,不用hashmap,我习惯这样写哈
  1. public class Solution {
  2.     /**
  3.      * @param A : A string includes Upper Case letters
  4.      * @param B : A string includes Upper Case letter
  5.      * @return :  if string A contains all of the characters in B return true else return false
  6.      */
  7.     public boolean compareStrings(String A, String B) {
  8.         // write your code here
  9.         if(A == null && B == null || A.length() == 0 && B.length() == 0)
  10.         {
  11.             return true;
  12.         }
  13.         
  14.         if(A == null || A.length() == 0)
  15.         {
  16.             return false;
  17.         }
  18.         
  19.         int[] result = new int[26];
  20.         
  21.         for(int i = 0; i < A.length(); i++)
  22.         {
  23.             result[A.charAt(i) - 'A']++;
  24.         }
  25.         
  26.          for(int j = 0; j < B.length(); j++)
  27.         {
  28.             if(result[B.charAt(j) - 'A'] == 0)
  29.             {
  30.                 return false;
  31.             }
  32.             result[B.charAt(j) - 'A']--;
  33.         }
  34.         return true;
  35.     }
  36. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 12:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表