加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 编程开发 > Java > 正文

java – 检查字符串是否由唯一字符组成的最简单的方法?

发布时间:2020-12-14 16:18:02 所属栏目:Java 来源:网络整理
导读:如果一个单词由唯一的字母组成(不区分大小写),我需要检查 Java.因为直接的解决方案是无聊的,我想出了: 对于字符串中的每个字符串,检查indexOf(char)== lastIndexOf(char). 将所有字符添加到HashSet,并检查是否设置size == string length. 将字符串转换为字
如果一个单词由唯一的字母组成(不区分大小写),我需要检查 Java.因为直接的解决方案是无聊的,我想出了:

>对于字符串中的每个字符串,检查indexOf(char)== lastIndexOf(char).
>将所有字符添加到HashSet,并检查是否设置size == string length.
>将字符串转换为字符数组,按字母顺序排序,循环遍历数组元素,并检查c [i] == c [i 1].

目前我最喜欢#2,好像最简单的方法.任何其他有趣的解决方案?

解决方法

我不喜欢1. – 这是一个O(N2)算法.你的2.大致是线性的,但总是遍历整个字符串.您的3.是O(N lg2 N),(可能)相对较高的常数 – 可能几乎总是比2慢.

但是,当您尝试在集合中插入一个字母,检查它是否已经存在时,我的偏好是,您可以立即停止.给定随机分配的字母,这应该只需要平均扫描一半的字符串.

编辑:两个注释都是正确的,正是您期望扫描的字符串的哪个部分将取决于分布和长度 – 在某些时候,字符串足够长,重复是不可避免的,(例如)一个字符不足那机会还是很高的.事实上,给定一个平坦的随机分布(即集合中的所有角色同样可能),这应该与生日悖论密切相关,这意味着碰撞的机会与可能的字符数的平方根有关字符集.例如,如果我们以相同的概率假设基本的US-ASCII(128个字符),我们将在大约14个字符处达到50%的碰撞几率.当然,在真正的字符串中,我们可能比它早一些,因为ASCII字符在大多数字符串中的任何接近于相同频率的位置都不被使用.

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读