当前位置: 网站首页 > 新闻中心 > 行业时讯 > 正文
2016/7/6 21:46:50

网站优化公司:如何确定一个字符串中是否所有字符全部互不相同

杭州宝三信息技术有限公司行业时讯编辑日期:2016/7/6 21:46:50

  首先需要想到的是,ASCII只有一个字节,意味着如果待检测的字符串长度超过了256位,那么这个字符串中一定有重复的元素。

  最简单的解法是将字符串中的每一个字符与剩下的字符比较,如果遇到相同的元素,则返回False,如果直到遍历结束都没有遇到相同元素,则返回True:

  def is_unique_char(string):

  str_len = len(string)

  if str_len > 256:

  return True

  for pos in xrange(str_len):

  for index in xrange(pos+1, str_len):

  if string[pos] == string[index]:

  return False

  return True

  这种解法的时间复杂度为O(n*n),空间复杂度为O(1)。当然很明显,这种解法的效率非常低下,有什么更好的实现呢?

  第二种解法是通过构建一个布尔值的数组,索引index表示ASCII码中值为index的字符。将初值置为False,如果某个元素第二次出现,则表示这个字符串出现了重复的字符,函数直接返回。这种解法的Python实现如下:

  def is_unique_char(string):

  if len(string) > 256:

  return True

  record = [False] * 256

  for ch in string:

  ch_val = ord(ch)

  if record[ch_val]:

  return False

  record[ch_val] = True

  return True

  上面代码的时间复杂度为O(n),空间复杂度为O(1)。不过,我们可以非常确定的是,n的最大值仅仅为256。

  如果考虑到Python的某些数据结构,则我们可以通过collections里的工具来实现:

  from collections import Counter

  is_unique_char = lambda s: True if len(s) > 256 else not bool(filter(lambda n: n > 1, Counter(s).values()))

  这些算法可能算不上最优解,不过根据题目,我们依次从比较容易的实现向比较复杂的实现再结合Python的集合类,让出题者了解了你的思考过程和对特定语言的工具集的使用。

  以上内容由杭州宝三信息技术有限公司整理发布,我们致力于互联网产品服务和技术开发与应用,专业为企事业单位提供一站式、全方位整合网络品牌服务。主营:SEO优化推广,网站建设,SEO网站优化,企业网站优化,百度排名优化等服务,联系电话0571-81383815.

您可能还对这些文章感兴趣:
关注杭州宝三信息技术有限公司