【字典树】 【哈希表】 【字符串】100251. 数组中的最短非公共子字符串

template<class TData = char, int iTypeNum = 26, TData cBegin = 'a'>
class CTrieNode
{
public:
  CTrieNode* AddChar(TData ele, int& iMaxID)
  {
#ifdef _DEBUG
    if ((ele < cBegin) || (ele >= cBegin + iTypeNum))
    {
      return nullptr;
    }
#endif
    const int index = ele - cBegin;
    auto ptr = m_vPChilds[ele - cBegin];
    if (!ptr)
    {
      m_vPChilds[index] = new CTrieNode();
#ifdef _DEBUG
      m_vPChilds[index]->m_iID = ++iMaxID;
      m_childForDebug[ele] = m_vPChilds[index];
#endif
    }
    return m_vPChilds[index];
  }
  CTrieNode* GetChild(TData ele)const
  {
#ifdef _DEBUG
    if ((ele < cBegin) || (ele >= cBegin + iTypeNum))
    {
      return nullptr;
    }
#endif
    return m_vPChilds[ele - cBegin];
  }
protected:
#ifdef _DEBUG
  int m_iID = -1;
  std::unordered_map<TData, CTrieNode*> m_childForDebug;
#endif
public:
  int m_iLeafIndex = -1;
protected:
  CTrieNode* m_vPChilds[iTypeNum] = { nullptr };
};
template<class TData = char, int iTypeNum = 26, TData cBegin = 'a'>
class CTrie
{
public:
  int GetLeadCount()
  {
    return m_iLeafCount;
  }
  CTrieNode<TData, iTypeNum, cBegin>* AddA(CTrieNode<TData, iTypeNum, cBegin>* par,TData curValue)
  {
    auto curNode =par->AddChar(curValue, m_iMaxID);
    FreshLeafIndex(curNode);
    return curNode;
  }
  template<class IT>
  int Add(IT begin, IT end)
  {
    auto pNode = &m_root;
    for (; begin != end; ++begin)
    {
      pNode = pNode->AddChar(*begin, m_iMaxID);
    }
    FreshLeafIndex(pNode);
    return pNode->m_iLeafIndex;
  } 
  template<class IT>
  CTrieNode<TData, iTypeNum, cBegin>* Search(IT begin, IT end)
  {
    auto ptr = &m_root;
    for (; begin != end; ++begin)
    {
      ptr = ptr->GetChild(begin);
      if (nullptr == ptr)
      {
        return nullptr;
      }
    }
    return ptr;
  }
  CTrieNode<TData, iTypeNum, cBegin> m_root;
protected:
  void FreshLeafIndex(CTrieNode<TData, iTypeNum, cBegin>* pNode)
  {
    if (-1 == pNode->m_iLeafIndex)
    {
      pNode->m_iLeafIndex = m_iLeafCount++;
    }
  }
  int m_iMaxID = 0;
  int m_iLeafCount = 0;
};
class Solution {
public:
  vector<string> shortestSubstrings(vector<string>& arr) {
    CTrie<> trie;
    for (const auto& s : arr)
    {
      const int n = s.size();
      m_vSubIndex.emplace_back(n + 1, vector<int>(n, -1));
      for (int left = 0; left < n; left++)
      {
        auto ptr = &trie.m_root;
        for (int len = 0; left + len < n; len++)
        {
          ptr = trie.AddA(ptr,s[left+len]);
          m_vSubIndex.back()[len + 1][left] = ptr->m_iLeafIndex;
          m_mIndexCount[ptr->m_iLeafIndex].emplace(m_vSubIndex.size());
        }
      }
    }
    vector<string> vRet;
    for (int i = 0; i < arr.size(); i++)
    {
      vRet.emplace_back(Cal(arr[i], i));
    }
    return vRet;
  }
  string Cal(const string& s, int index)
  {
    auto& v = m_vSubIndex[index];
    const int n = s.size();
    for (int len = 1; len <= n; len++)
    {
      set<string> sets;
      for (int left = 0; left < n; left++)
      {
        const int index = v[len][left];
        if (1 == m_mIndexCount[index].size())
        {
          sets.insert(s.substr(left, len));
          if (sets.size() > 1)
          {
            sets.erase(std::prev(sets.end()));
          }
        }
      }
      if (sets.size())
      {
        return *sets.begin();
      }
    }
    return "";
  }
  vector<vector<vector<int>>> m_vSubIndex;
  unordered_map<int, unordered_set<int>> m_mIndexCount;
  int m_r, m_c;
};

template<class T, class T2>
void Assert(const T& t1, const T2& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{
  vector<string> arr;
  {
    Solution sln;
    arr = { "vbb", "grg", "lexn", "oklqe", "yxav" };
    auto res = sln.shortestSubstrings(arr);
    Assert({ "b","g","n","k","a" }, res);
  }
  {
    Solution sln;
    arr = { "cab", "ad", "bad", "c" };
    auto res = sln.shortestSubstrings(arr);
    Assert({ "ab","","ba","" }, res);
  }
  {
    Solution sln;
    arr = { "abc", "bcd", "abcd" };
    auto res = sln.shortestSubstrings(arr);
    Assert({ "","","abcd" }, res);
  }
}