首页 > 试题广场 >

确定字符互异

[编程题]确定字符互异

热度指数：95597 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个字符串string iniString，请返回一个bool值,True代表字符串的所有字符全都不同，False代表存在相同的字符。保证字符串中的字符为ASCII字符且不允许使用额外的存储结构，字符串的长度小于等于3000。大小写字母算不同的字符

测试样例：

"aeiou"

返回：True

"BarackObama"

返回：False

算法知识视频讲解

查看答案及解析

推荐

Bug祥

public boolean checkDifferent(String iniString) {   
return !iniString.matches(".*(.)(.*\\1).*");
}

编辑于 2016-02-24 11:33:12 回复(87)

Java

牛客338185493号

public class Different {
    public boolean checkDifferent(String iniString) {
        // write code here
        if (iniString == null || iniString.length() <= 1) {
            return true;
        }

        if (iniString.length() > 256) {
            return false;
        }

        //使用了256个字节额外空间, 不符合要求, 没办法
//         int[] bitMap = new int[256];
//         for (int i = 0; i < iniString.length(); i++) {
//             if (bitMap[iniString.charAt(i) - ' '] == 0) {
//                 bitMap[iniString.charAt(i) - ' '] = 1;
//             } else {
//                 return false;
//             }
//         }
        //由于java的对象只是引用, 因此不能像C/c++一样直接进行内存访问, finally修饰不可变
        //所以排序不可能不产生额外空间, 那么只剩下遍历了, 两次迭代O(n^2)
        //速度差不多, 省了内存, 因为ascii不可能超过256长度, 本质上是O(1)时间复杂度, O(1)空间复杂度
        for (int i = 0; i < iniString.length() - 1; i++) {
            char c = iniString.charAt(i);

            for (int j = i + 1; j < iniString.length(); j++) {
                if (c == iniString.charAt(j)) {
                    return false;
                }
            }
        }

        return true;
    }
}

发表于 2021-12-31 22:18:11 回复(0)

Java

微醺0.0

import java.util.*;

public class Different {
    public boolean checkDifferent(String iniString) {
        if (iniString.length() > 256) {
            return false;
        }

        boolean[] chars = new boolean[256];
        for(char item : iniString.toCharArray()) {
            if (chars[item]) {
                return false;
            }
            chars[item] = true;
        }

        return true;
    }
}

发表于 2021-12-18 12:24:01 回复(0)

Java

牛客117772105号

import java.util.*;

public class Different {
    public boolean checkDifferent(String iniString) {
        // write code here
        Set<Character> set = new HashSet();
        char[] a = iniString.toCharArray();
        for(int i = 0; i < a.length; i++){
        if(!set.add(a[i]))
            return false;
        }
        return true;
    }
}

发表于 2021-05-02 14:03:14 回复(0)

Java

牛客196305255号

反向查找即可。

public class Different {
    public boolean checkDifferent(String iniString) {
        for(int i=0;i<iniString.length();i++){
            String s=iniString.substring(i,i+1);
            int index=iniString.lastIndexOf(s);
            if(index!=i){
                return false;
            }
        }
        return true;
    }
}

发表于 2020-11-30 20:30:49 回复(0)

Java

牛客445701793号

import java.util.*;

public class Different {
    public boolean checkDifferent(String iniString) {
        
        if(iniString.length() > 3000) return false;
        
        boolean[] char_set = new boolean[256];
        for(int i = 0;i < iniString.length();i++) {
            int val = iniString.charAt(i);
            if(val > 256 ||char_set[val] == true){//
                return false;
            }
            char_set[val] = true;
        }
        return true;
    }
}

发表于 2020-08-13 21:20:07 回复(0)

Java

牛客280978516号

import java.util.*;
//利用了直接插入的思想比较
public class Different {
     public boolean checkDifferent(String iniString) {
        //将字符串转换位字符数组
        char[] c = iniString.toCharArray();          
        boolean flag = true;
        for(int i=1; i<iniString.length(); i++){
            if (flag == false)
                break;
            char temp = c[i];
            for(int j=i-1; j>=0; j--){
                if(c[j] == temp){
                    flag = false;
                    break;
                }
            }
        }
        return flag;
    }
    public static void main(String[] args) {
        Different test = new Different();
        String s1 = "aeiou";
        System.out.println(test.checkDifferent(s1));
        String s2 = "BarackObama";
        System.out.println(test.checkDifferent(s2));
    }
}

发表于 2020-05-10 11:39:34 回复(0)

Java

笑看一生ね

int val = iniString.charAt(i);
                if(charset[val]){
                    return false;
                }
                charset[val] = true;

这段看不懂，希望有大佬能帮忙解答一下

发表于 2020-04-15 12:08:33 回复(0)

Java

7EdgXiao

public boolean checkDifferent(String iniString) {
int len = iniString.length();
for(int i = 0; i< len; i++){
if(iniString.lastIndexOf(iniString.charAt(i)) != i){
return false;
}
}
return true;
}

发表于 2020-03-17 14:42:37 回复(0)

Java

1411527964

O(n) 的方法。

既然都是ascii，将字符串遍历256遍，如果其中一个字符出现了两次，返回false，否则返回true。

    public boolean checkDifferent(String iniString) {
        // write code here
        char c=(char) 0;
        int length=iniString.length();
        for(int i=0;i<256;i++){
            boolean flag=false;
            for(int j=0;j<length;j++){
                if(c==iniString.charAt(j)){
                    if(flag){
                      return false;
                    }else{
                      flag=true;
                    }
                }
            }
            c++;
        }
        return true;
    }

编辑于 2020-03-16 17:14:15 回复(0)

Java

猫哥💋

双指针法这时间复杂度是O(n) 还是O(n2) ?

import java.util.*;

public class Different {
public boolean checkDifferent(String iniString) {
// write code here
int i = 0;
for (int j = i + 1; j < iniString.length(); j++) {
if (iniString.charAt(j) == iniString.charAt(i)) {
return false;
}
//j 到达尾部 i++
if (j == iniString.length()-1) {
i++;
//i到达尾部算法结束
if (i == iniString.length()-1) {
return true;
}
j = i+1;
}
}
return true;
}
}

编辑于 2020-03-17 09:52:42 回复(0)

Java

天山剑客

//两层循环暴力搜素，有相同的字符就返回false，否则返回true，时间复杂度O(n^2)
public class Different {
    public boolean checkDifferent(String iniString) {
        // write code here
    	
    	for (int i = 0; i < iniString.length() - 1; i++) {
    		for (int j = i + 1; j < iniString.length(); j++) {
    			if (iniString.charAt(i) == iniString.charAt(j)) {
    				return false;
    			}
    		}
    	}
    	
    	return true;
    }
}

发表于 2019-12-11 22:58:33 回复(0)

Java

Westbrooooooook

import java.util.*;

public class Different {
    public boolean checkDifferent(String iniString) {
        for(int i=0;i<iniString.length();i++){

            for(int j=i+1;j<iniString.length();j++){
                if (iniString.charAt(j)==iniString.charAt(i))
                {
                    return false;
                }
            }
        }
        return true;
        // write code here
    }
}

发表于 2019-09-06 11:00:55 回复(0)

Java

共勉13

图片说明

发表于 2019-07-05 12:18:43 回复(0)

Java

吃了开心果就开心了

我转为ascii再用两个集合的长度互相比较不可以吗？

public static void main(String[] args) {

String str = "abdcxc";

toAsscii(str);

}

public static void toAsscii(String str) {

char[] c = str.toCharArray();

List<Integer> list = new ArrayList<>();

for (int i = 0; i < c.length; i++) {

list.add((int) c[i]);

}

Set<Integer> set = new HashSet<>(list);

if(list.size() == set.size()) {

System.out.println(true);

}else {

System.out.println(false);

}

请大神们指点

发表于 2019-05-08 01:06:43 回复(0)

Java

J.YX

public class Different {
    public boolean checkDifferent(String iniString) {
        for (int i = 0; i < iniString.length(); i++) {
            for (int j = i + 1; j < iniString.length(); j++) {
                if (iniString.charAt(i) == iniString.charAt(j)) {
                    return false;
                }
            }
        }
        return true;
    }
}

发表于 2019-03-19 15:18:55 回复(0)

Java

postback

import java.util.*;

public class Different {
    public boolean checkDifferent(String iniString) {
        // write code here
        char[] charArray = iniString.toCharArray();
        int len = (charArray.length-1);
        for(int i=0;i<len;i++){
            char a = charArray[i];
            if(iniString.lastIndexOf(a)!=i)return false;
        }
        return true;
    }

发表于 2019-01-11 22:24:51 回复(0)

Java

wero

public class Different {
    public boolean checkDifferent(String iniString) {
        //先排序，然后检查相邻两个字符
        char[] iniChars = iniString.toCharArray();
        Arrays.sort(iniChars);
        int j = 0;
        for (int i=1; i<iniChars.length; i++){
            if (iniChars[i] == iniChars[j]){
                return false;
            }
            j++;
        }
        return true;
    }
}

编辑于 2018-12-04 19:36:24 回复(1)