這題看了別人討論才做出來。
暴力法：枚舉所有的矩形，然后統(tǒng)計各個矩形中的字符數(shù)。這樣時間復(fù)雜度O(n^12)必然超時。
可以反過來考慮問題，對于矩形中的每一個單元，會有多少個矩形包含它。
這樣思考，問題就很簡單了：
一個矩形可以由它的左上角和右下角唯一決定。
而若某單元(x,y)包括在某矩形中，那么，這個矩形的左上角(x',y')必然為(0<=x'<=x),(0<=y'<=y).
右上角(x'',y'')必然為(x<=x''<c),(y<=y''<r).c為總列數(shù),r為總行數(shù)。
這樣的矩形顯然有(x+1)(y+1)(c-x)(c-y)個。(坐標(biāo)均為0-based)
代碼如下：
???class?SubrectanglesOfTable
??????????????{?
??????????????public:?
??????????????vector<long?long>?getQuantity(vector?<string>?t)?
??????????????????{?
??????????????????????????vector<long?long>?res(26);???
??????????????????????????
??????????????????????????for(int?i=0;i<t.size();++i)
?????????????????????????????? t[i]+=t[i];
??????????????????????????
??????????????????????????int?tmp?=?t.size();
??????????????????????????for(int?i=0;i<tmp;++i)
????????????????????????????t.push_back(t[i]);???????????????????????????????
????????????????????????????
??????????????????????????int?r?=?t.size();
??????????????????????????int?c?=?t[0].size();
??????????????????????????
??????????????????????????for(int?i=0;i<r;++i)
???????????????????????????? for(int?j=0;j<c;++j){
??????????????????????????????????res[?t[i][j]-'A']+=(i+1)*(j+1)*(r-i)*(c-j);???????????????
??????????????????????????????????}???
?????????????????????????????
????????????????????????? return?res;???????????????????????????????? ???????????????????????????????
??????????????????}
｝
其實不需要生成字符串的四個拷貝。