A C# DFS Solution after Building a Palindrome 2D Graph -- Self Explained Code


  • 0
    L
    public IList<IList<string>> Partition(string s) {
        byte[,] grid = new byte[s.Length, s.Length];
        //1. Construct Palindrom Map grid[i, j] == 1 means palindrome at s's index from i to j
        for(int i = 0; i < s.Length; i++)
        {
            for(int j = 0; i + j < s.Length && i - j >= 0; j++)
                if(s[i - j] == s[i + j]) grid[i-j, i+j] = 1;
                else break;
            for(int j = 1; i + j < s.Length && i - j + 1 >= 0; j++)
                if(s[i - j + 1] == s[i + j]) grid[i-j+1, i+j] = 1;
                else break;
        }
        //2. DFS the palindrome map to build all results
        IList<IList<string>> result = new List<IList<string>>();
        printResult(result, new List<string>(), 0, grid, s);
        return result;
    }
    
    private void printResult(IList<IList<string>> result, List<string> soFar, int nextPos, byte[,] grid, string obj)
    {
        if(nextPos == grid.GetLength(0))
        {
            IList<string> newLst = new List<string>(soFar);
            result.Add(newLst);
        }
        else
            for(int i = nextPos; i < grid.GetLength(1); i++)
                if(grid[nextPos, i] == 1)
                {
                    soFar.Add(obj.Substring(nextPos, i - nextPos + 1));
                    printResult(result, soFar, i + 1, grid, obj);
                    soFar.RemoveAt(soFar.Count - 1);
                }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.