LintCode刷题之路(一)
博客专区 > StayY 的博客 > 博客详情
LintCode刷题之路(一)
StayY 发表于1年前
LintCode刷题之路(一)
  • 发表于 1年前
  • 阅读 23
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 新注册用户 域名抢购1元起>>>   

在算法和数据结构上,我觉得我是一个彻彻底底的小白,开始刷题吧。

#阶梯训练

###1. 两个字符串是变位词

######写出一个函数 anagram(s, t) 判断两个字符串是否可以通过改变字母的顺序变成一样的字符串。

样例

给出 s = "abcd",t="dcab",返回 true.

给出 s = "ab", t = "ab", 返回 true.

给出 s = "ab", t = "ac", 返回 false.

> 首先看到这个题目 我们想到的就是字符串排序了,通过排序把字符调换成有顺序的字符串,再来比较。

所以就会出现以下代码

public class Solution {
    /**
     * @param s: The first string
     * @param b: The second string
     * @return true or false
     */
    public boolean anagram(String s, String t) {
        //先查看长度是否相等,不相等则返回false
        if(s.length() != t.length()){
            return false;
        }
        //转换成字符 然后排序
        char[] sChar = s.toCharArray();
        char[] tChar = t.toCharArray();
        Arrays.sort(sChar);
        Arrays.sort(tChar);
        for(int i=0;i<s.length();i++){
            if(sChar[i]!=tChar[i]){
                return false;
            }
        }
        return true;
    }
};

由于以上是两个字符串之间的比较,所以就能很方便的这样用,但是如果是多个字符串数组又是怎么比较的呢,这个问题后面会有。

九章算法提供的答案是

public class Solution {
    /**
     * @param s: The first string
     * @param b: The second string
     * @return true or false
     */
    public boolean anagram(String s, String t) {
        if (s.length() != t.length()) {
           return false;
        }
        
        int[] count = new int[256];
        for (int i = 0; i < s.length(); i++) {
            count[(int) s.charAt(i)]++;
        }
        for (int i = 0; i < t.length(); i++) {
            count[(int) t.charAt(i)]--;
            if (count[(int) t.charAt(i)] < 0) {
                return false;
            }
        }
        return true;
    }
};

> 这个方法是用一个数组存放 把字符串中的字符用数组记录下来 先把第一个字符串的字符通过数组记录下来,数组中存在就+1,再用第二个数组的索引去减1,如果有小于0的值出现,就说明两个字符串不相等。

共有 人打赏支持
粉丝 0
博文 34
码字总数 21515
×
StayY
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: