Leetcode: Code Testcase Test Result Test Result 2977. Minimum Cost to Convert String II

#include <string>
#include <vector>
#include <optional>
#include <unordered_set>
#include <unordered_map>

class Solution
{
public:
    using Type = std::uint64_t;
    using ValueType = std::optional<Type>;
    using Row = std::vector<ValueType>;
    using Graph = std::vector<Row>;
    const ValueType INF = std::nullopt;

    long long minimumCost(std::string source,
        std::string target,
        std::vector<std::string>& original,
        std::vector<std::string>& changed,
        std::vector<int>& cost)
    {
        _source = source;
        _target = target;
        fillGraph(original, changed, cost);

        auto result = calculate();
        return result ? result.value() : -1;
    }

    void fillGraph(const std::vector<std::string>& original,
        const std::vector<std::string>& changed,
        const std::vector<int>& cost)
    {
        std::unordered_set<std::string> nodesSet;
        for (int i = 0; i < original.size(); i++)
        {
            nodesSet.insert(original[i]);
            nodesSet.insert(changed[i]);
        }

        int index = 0;
        for (const auto& node : nodesSet)
        {
            _nodeIndex[node] = index++;
        }

        _graph = Graph(nodesSet.size(), Row(nodesSet.size(), INF));
        for (int i = 0; i < original.size(); i++)
        {
            int fromIndex = _nodeIndex[original[i]];
            int toIndex = _nodeIndex[changed[i]];

            ValueType& currentValue = _graph[fromIndex][toIndex];
            if (!currentValue || currentValue > cost[i])
            {
                currentValue = cost[i];
            }
            _lengths.insert(original[i].size());
        }
        _lengths.insert(1);

        floydWarshall();
    }

    void floydWarshall()
    {
        for (int k = 0; k < _graph.size(); k++)
        {
            for (int i = 0; i < _graph.size(); i++)
            {
                for (int j = 0; j < _graph.size(); j++)
                {
                    auto ik = _graph[i][k];
                    auto ij = _graph[i][j];
                    auto kj = _graph[k][j];
                    if (ik && kj)
                    {
                        if (!ij || ij.value() > ik.value() + kj.value())
                        {
                            _graph[i][j] = ik.value() + kj.value();
                        }
                    }
                }
            }
        }
    }

    ValueType calculate()
    {
        std::vector<ValueType> results = std::vector<ValueType>(_source.size(), INF);

        for (int i = 0; i < _source.size(); i++)
        {
            for (const int length : _lengths)
            {
                ValueType prevValue = getPrev(results, i, length);
                if (prevValue)
                {
                    std::string from = _source.substr(i - length + 1, length);
                    std::string to = _target.substr(i - length + 1, length);
                    ValueType currentValue = getCurrentValue(from, to);
                    results[i] = Min(results[i], plus(prevValue, currentValue));
                }
            }
        }

        return *results.crbegin();
    }

    ValueType plus(const ValueType& a, const ValueType& b)
    {
        if (!a || !b)
        {
            return INF;
        }
        return a.value() + b.value();
    }

    ValueType getCurrentValue(const std::string& from, const std::string& to)
    {
        ValueType currentValue = std::nullopt;
        if (from == to)
        {
            currentValue = 0;
        }
        else
        {
            int i, j;
            if (getIndex(from, i) && getIndex(to, j))
            {
                currentValue = _graph[i][j];
            }
        }

        return currentValue;
    }

    bool getIndex(const std::string& key, int& outIndex)
    {
        auto iter = _nodeIndex.find(key);
        if (iter != _nodeIndex.end())
        {
            outIndex = iter->second;
            return true;
        }
        return false;
    }

    ValueType getPrev(const std::vector<ValueType>& results, int currentIndex, int length)
    {
        int prevIndex = currentIndex - length;
        if (prevIndex >= 0)
        {
            return results[prevIndex];
        }
        else if (prevIndex == -1)
        {
            return 0;
        }
        return INF;
    }

    const ValueType& Min(const ValueType& a, const ValueType& b)
    {
        if (!a)
        {
            return b;
        }
        if (!b)
        {
            return a;
        }
        return std::min(a, b);
    }

private:
    std::string _source;
    std::string _target;
    std::unordered_map<std::string, int> _nodeIndex;
    std::unordered_set<int> _lengths;
    Graph _graph;
};

class SolutionFast
{
public:
    using Type = std::uint64_t;
    using ValueType = std::optional<Type>;
    using Graph = std::vector<ValueType>;
    const ValueType INF = std::nullopt;

    long long minimumCost(std::string& source,
        std::string& target,
        std::vector<std::string>& original,
        std::vector<std::string>& changed,
        std::vector<int>& cost)
    {
        _source = std::move(source);
        _target = std::move(target);

        fillGraph(original, changed, cost);

        auto result = calculate();

        if (!result)
        {
            return -1;
        }
        return result.value();
    }

    ValueType& getValue(int i, int j)
    {
        return _graph[i * _nodeIndex.size() + j];
    }

    const ValueType& getValue(int i, int j) const
    {
        return _graph[i * _nodeIndex.size() + j];
    }

    void fillGraph(const std::vector<std::string>& original,
        const std::vector<std::string>& changed,
        const std::vector<int>& cost)
    {
        std::unordered_set<std::string_view> nodesSet;
        for (int i = 0; i < original.size(); i++)
        {
            nodesSet.insert(original[i]);
            nodesSet.insert(changed[i]);
        }

        int index = 0;
        for (const auto& node : nodesSet)
        {
            _nodeIndex[node] = index++;
        }

        _graph = Graph(nodesSet.size() * nodesSet.size(), INF);

        for (int i = 0; i < original.size(); i++)
        {
            int fromIndex = _nodeIndex[original[i]];
            int toIndex = _nodeIndex[changed[i]];

            const ValueType& currentValue = getValue(fromIndex, toIndex);
            if (currentValue && currentValue > cost[i] || (!currentValue))
            {
                getValue(fromIndex, toIndex) = cost[i];
            }
            _lengths.insert(original[i].size());
        }

        _lengths.insert(1);

        floyd();
    }

    void floyd()
    {
        for (int k = 0; k < _nodeIndex.size(); k++)
        {
            for (int i = 0; i < _nodeIndex.size(); i++)
            {
                const auto& ik = getValue(i, k);
                for (int j = 0; j < _nodeIndex.size(); j++)
                {
                    auto& ij = getValue(i, j);
                    const auto& kj = getValue(k, j);

                    if (ik && kj)
                    {
                        if (ij)
                        {
                            if (ij.value() > ik.value() + kj.value())
                            {
                                ij = ik.value() + kj.value();
                            }
                        }
                        else [[likely]]
                        {
                            ij = ik.value() + kj.value();
                        }
                    }
                }
            }
        }
    }

private:
    ValueType Min(const ValueType& a, const ValueType& b) const
    {
        if (!a)
        {
            return b;
        }
        if (!b)
        {
            return a;
        }

        return std::min(a.value(), b.value());
    }

    ValueType getPrev(const std::vector<ValueType>& result, int currentIndex, int length) const
    {
        int prevIndex = currentIndex - length;
        if (prevIndex >= 0)
        {
            return result[prevIndex];
        }
        else if (prevIndex == -1)
        {
            return 0;
        }
        return INF;
    }

    ValueType plus(ValueType a, ValueType b) const
    {
        if (!a || !b)
        {
            return INF;
        }
        return a.value() + b.value();
    }

    bool getIndex(const std::string_view& key, int& outIndex) const
    {
        auto iter = _nodeIndex.find(key);
        if (iter != _nodeIndex.end())
        {
            outIndex = iter->second;
            return true;
        }
        return false;
    };

    ValueType getCurrentValue(const std::string_view& from, const std::string_view& to) const
    {
        ValueType currentValue = std::nullopt;
        if (from == to)
        {
            currentValue = 0;
        }
        else
        {
            int i, j;
            if (getIndex(from, i) && getIndex(to, j))
            {
                currentValue = getValue(i, j);
            }
        }

        return currentValue;
    };

    ValueType calculate()
    {
        _results = std::vector<ValueType>(_source.size(), INF);

        int maxLength = *_lengths.crbegin();

        for (int i = 0; i < _source.size(); i++)
        {
            for (const int length : _lengths)
            {
                ValueType prevValue = getPrev(_results, i, length);
                if (prevValue)
                {
                    std::string_view from(_source.data() + (i - length + 1), length);
                    std::string_view to(_target.data() + (i - length + 1), length);
                    ValueType currentValue = getCurrentValue(from, to);
                    _results[i] = Min(_results[i], plus(prevValue, currentValue));
                }
            }
        }

        return *_results.crbegin();
    }

    std::string _source;
    std::string _target;

    Graph _graph;
    std::set<int> _lengths;
    std::vector<ValueType> _results;
    std::unordered_map<std::string_view, int> _nodeIndex;
};