字符串中最常见的字符和字符串的排列

上周，我非常荣幸地访问了Spotify办公室，在那里我有机会与那里的一些很棒的工程师聊天。 我认为写自己的经验对我来说是有益的，最重要的是，将其记录为改进的平台。 在本文中，我将介绍与字符串有关的算法，特别是在字符串中搜索字符，并创建给定字符串的所有可能排列。

字符串中最常见的字符

首先，让我们从查找字符串中最常见的字符开始。 例如，字符串“ Manhattan”应返回“ a”，因为字母“ a”是最常见的，计数为三。 创建函数时，我的目标是始终弄清楚参数是什么。 在这里，我们正在输入一个字符串，并且我们的函数应该返回一个字符。

接下来，我的方法是将字符串分成字符数组。 通过这样做，我可以遍历字符数组并检查哪个字符的频率最高。 为了进行检查，我们必须具有某种计数器来跟踪哪个字符的频率最高。 另外，在搜索该字符时如何访问？ 最初，这让我感到难过，直到我不得不翻阅数组并更多地考虑其他可能的数据结构。 在这种情况下，我们可以使用字典，其中我们的键是一个字符，而我们的值是它在单词中出现的频率。

以下是我最终得到的结果：

  func returnMostCommonCharacter（string：String）->字符{ 

  var个字符= Array（string.characters） 
  var dict =字典（） 
  var maxCharacter =个字符[0] 
  var maxCount = 0 

 字符中的字符{ 
 如果让我们看到CharCount = dict [character] { 
  dict [character] = seenCharCount + 1 

 如果dict [character]！  > maxCount { 
  maxCharacter =字符 
  maxCount = dict [character]！ 
  } 
  }其他{ 
  dict [字符] = 1 
  } 
  } 

 返回maxCharacter 

  } 

如您所见，我们正在输入一个字符串并返回一个字符。 接下来，我们将字符串转换为字符数组。 我们还有一个字典，其中包含key：character和value：integer。 接下来，我们有一个maxCharacter变量，它将用作频率或出现频率最高的字母。 现在，默认值为数组中的第一个字母。 如果一个单词具有所有唯一字符，那么我们将始终返回字符数组中的第一个字母。 最后，我们有一个maxCount变量，我们将使用它来监视最频繁的字母的计数。

当我们遍历字符数组时，我们增加seenCharCount的计数，并使用它为字符键分配一个Int值。 另外，我们添加了一个if语句，如果字符键的值大于maxCount，最初为零，则将maxCharacter分配为该当前字符以及maxCount。

字符串的排列

当我最初尝试排列时，我一直尝试以迭代方式或递归方式来解决问题。 另外，我的主要目的是交换字符并返回所有可能的初始字母版本。 如果您只想创建具有相同数量的字母的单词，那么这很好，但是如果您试图获得所有可能的结果，则不会那么多。 例如，如果我们使用“ cat”一词，我最初的想法是交换所有字母并将它们返回为“ cat”，“ cta”，“ tac”，“ tca”，“ act”，“ atc”。但是，诸如“ at”或“ ct”之类的其他可能单词呢？这里想到的数据结构是一棵树，其中有一个根，并且C，A，T的子节点和这些节点的下面都有节点他们所有可能的剩余字母。 我们主要讨论了此数据结构，以直观地了解如何最终获得字符串的所有排列，这是通过创建递归函数实现的。

我决定进行研究并了解排列算法的不同形式，并对其进行测试以寻找乐趣，并明确地学习。

最终我得到了以下算法：

  func permute（list：[String]，minStringLen：Int = 1）-> Set  { 

  func permute（fromList：[String]，toList：[String]，minStringLen：Int，set：inout Set ）{ 

 如果toList.count> = minStringLen { 
  set.insert（toList.joined（分隔符：“”）） 
  } 

 如果！fromList.isEmpty { 
 对于fromList.enumerated（）中的（索引，项目）{ 
  var newFrom = fromList 
  newFrom.remove（at：index） 
  permute（fromList：newFrom，toList：toList + [item]，minStringLen：minStringLen，设置：＆set） 
  } 
  } 
  } 

  var set = Set （） 

  permute（fromList：list，toList：[]，minStringLen：minStringLen，设置：＆set） 

 返回集 

  } 

如您所见，整个置换函数中较长的置换函数被多次调用。 这里的总体思想是拥有两个不同的字符串列表或字符串数​​组，分别是fromList和toList，从从未使用过的字母到已构建的字符串。 当字符串的长度大于1时，我们使用递归将字符串添加到该函数的输出集中。您可以通过将minStringLen整数更改为2或更大（取决于最小字符数）来轻松更改此字符串您想归还一组。 我故意将其保留为1，以查看所有可能的回报，包括各个字母本身。

需要注意的一件事是，由于返回值是一组，所以它不会是有序的。 通过创建新变量并将集合强制转换为数组，可以轻松将其转换为数组。

直观地查看结果

下面是Xcode中的一个快速模型，其中有一个文本字段，它将作为字符串输入，一旦按下convert按钮，我们将按顺序排列所有可能的排列以及字符串中最常见的字符，以进行更新。

以下是我最终得到的结果：

“你好”一词有两个L，这是最常见的字母。 通过表格视图，您可以了解除4个字母排列之外还有更多的元素。

可以通过以下github存储库随意克隆和测试自己。 谢谢！

https://github.com/ezaman/algoFun/tree/master