Explanation in simple english and solution in C#


  • 0
    A

    First think of a worst case input:
    abcdefgh
    In this case, there's no scope of optimization as all characters are different. Hence printer would print character by character.

    Now consider a slightly better case:
    abcdafgh
    In above input, notice that character 'a' is repeated. So, you could visualize that printer should first type 'a' till position 4 (0 index based) to print in minimal turns.

    Try to generalize above solution for range p to r substring. It should me

    • minimum of P[p+1, r] + 1 (case where we assume that first character should not be optimized at all).
    • minimum of (P[p, q-1], P[q+1, r]) where q ranges from p+1 to r and s[p] equals s[q]. In this case, we are trying all combinations by optimizing for position p.
    • Finally P[p,r] is minimum of above two calculations.
    public int StrangePrinter(string s) {
            if (string.IsNullOrEmpty(s))
            {
                return 0;
            }
            
            int[,] P = new int[s.Length, s.Length];
            for (int i=0; i < s.Length; i++)
            {
                P[i,i] = 1;
            }
            
            for (int l=2; l <= s.Length; l++)
            {
                for (int p = 0; p < s.Length - l + 1; p++)
                {
                    int r = p + l - 1;
                    
                    int min = P[p + 1, r] + 1;
                    
                    for (int q = p + 1; q <= r; q++)
                    {
                        if (s[p] == s[q])
                        {
                            int sum = P[p, q-1];
                            if (q != r)
                            {
                                sum += P[q+1, r];
                            }
                            
                            if (sum < min)
                            {
                                min = sum;
                            }
                        }
                    }
                    
                    P[p,r] = min;
                }
            }
            
            return P[0, s.Length-1];
        }
    

Log in to reply
 

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